Under construction

Still being built. Things may change

Festival

Interview

Time limit2sMemory limit512 MB

Summary
Pick exactly one non-overlapping show from each of up to 10 stages so the total known-song count is maximized, or report -1 if no valid selection exists.
Level

Medium7 of 10

Topics
Dynamic programming, Bit manipulation, Intervals, Sorting
Solved
No attempts yet

Problem

Music festivals should be pure fun, but some of them grow so large that they become a headache for attendees. The problem is that so many good acts play on so many stages that even the simple task of choosing which shows to watch becomes complicated.

To help attendees of such festivals, Fulano decided to create an app that, after evaluating the songs heard on their favorite streaming services, suggests which shows to watch so that no other combination of shows is better according to the criteria below:

  • To get the most out of the experience, it is important to watch each chosen show in full.
  • Going to the festival and not seeing one of the stages is out of the question.
  • To ensure the artist selection matches the user, the app counted how many songs by each artist the user knows from having heard them on streaming services. The total number of known songs by the chosen artists must be as large as possible.

Unfortunately, the beta version of the app received several criticisms, because users managed to think of better selections than the ones suggested. Your task in this problem is to help Fulano and write a program that, given the descriptions of the shows happening on each stage, computes the ideal list for the user.

Travel time between stages is ignored. So as long as no two chosen shows overlap in time, it is considered possible to watch all of them in full. In particular, if one show ends exactly when another begins, it is possible to watch both.

Input

The first line contains an integer 1 ≤ N ≤ 10 representing the number of stages. The next N lines describe the shows happening on each stage. The i-th of them consists of an integer Mi ≥ 1, representing the number of shows scheduled for the i-th stage, followed by Mi show descriptions. Each show description contains 3 integers ij, fj and oj (1 ≤ ij < fj ≤ 86400 and 1 ≤ oj ≤ 1000), representing respectively the start and end times of the show and the number of songs by the performing artist that the user has previously heard. The sum of the Mi will not exceed 1000.

Output

Your program must produce a single line with an integer representing the total number of previously heard songs by the chosen artists, or −1 if there is no valid solution.

Examples2

  1. Example 1

    Input
    3
4 1 10 100 20 30 90 40 50 95 80 100 90
1 40 50 13
2 9 29 231 30 40 525
    Expected output
    859

  2. Example 2

    Input
    3
2 13 17 99 18 19 99
2 13 14 99 15 20 99
2 13 15 99 18 20 99
    Expected output
    -1