408775: GYM103306 J John in the Amusement Park

In an amusement park there are $$$A$$$ different activities where people can participate to improve their happiness. Each activity $$$i$$$ in the park has a fixed duration $$$d_i$$$ in minutes, and provides an amount of $$$h_i$$$ happiness. Since the activities require some preparation they are offered to be started at certain times in the day while the park is opened. The times at which an activity can be started are given in minutes since the park opening, this is, if an activity is listed as it can be started at $$$10$$$ it means the activity starts $$$10$$$ minutes after the park opening.

John has been very tired from work this week and decided to go to the amusing park to get some happiness participating in certain activities, but, as next week seems to be a very complicated work week, John wants to select the activities in such way that the total happiness of participating on those activities during the day is maximized. The total happiness John can get from participating in the activities equals the sum of happiness each activity provides for participating in it. John believes that two rules should be followed to achieve maximum happiness:

• John will not start an activity until the activity he is participating finishes.
• John will not start an activity after the park closing time, but, the last activity may be finished after the park closing time.

Given the closing time of the park, the number of activities in the park, their duration and starting times, can you help John find the maximum happiness he can get from his visit to the amusement park?

The first line of input contains two integer numbers separated by a space $$$A$$$ ($$$1 \leq A \leq 500$$$) and T ($$$1 \leq T \leq 10^6$$$), representing the number of activities in the amusing park, and the minute at which the park closes. The next $$$2\times A$$$ lines describe each of the park activities. Each activity is described in two lines of input. The first of these two lines contains three integer numbers separated by a space $$$h_i$$$, $$$d_i$$$, $$$t_i$$$ ($$$1 \leq h_i \leq 1000$$$, $$$1 \leq d_i \leq T$$$, $$$1 \leq t_i \leq 10$$$), representing, respectively, the happiness $$$h_i$$$ and duration $$$d_i$$$ of the $$$i$$$-th activity, and the $$$t_i$$$ number of different times when the $$$i$$$-th activity can be started. The second description line for an activity contains $$$t_i$$$ integer numbers separated by a space, representing each of the times $$$t_{i,j}$$$ when the activity can be started ($$$0 \leq t_{i,j} < T$$$). It is guaranteed that the times for each activity will be given in increasing order, this is $$$t_{i,j} < t_{i,j+1}$$$ where $$$1 \leq j \leq t_i$$$.

Print a single line with an integer number, the maximum number of happiness John can get in a day in the park.

3 100
40 10 3
0 40 60
100 80 2
0 20
50 15 1
1

150