skills, each with
levels. Each level of a skill has its own training time and experience value gained from improving that skill. However, the levels of a skill have to be upgraded in succession, i.e. you have to have upgraded the previous level of a skill before continuing. , being a passionate programmer, wants to maximize his experience earned in a given amount of time. In fact, as is very indecisive, he wants to know the maximum amount of experience he can gain in
amount of time.
Input Specification
The first line of input will contain two integers, and
. The next
lines will be in the format
. Where
represents the number of levels for each skill and
and
represent the time needed to complete the level and the experience gained from completing the level, respectively.
Constraints
Output Specification
A single integer for the maximum experience that
can gain in the given amount of time.Sample Input
3 20
2 10 1 10 19
1 10 10
1 20 15
Sample Output
20
Explanation for Sample Output
Although skill 3 is a good choice to upgrade, upgrading level 1 and 2 of skill 1 is the best choice.
Comments
I'm probably misinterpreting the constraints, but the time for the levels exceeds the given max time for the last 2 test cases.
I think it goes higher than 10
Yes it goes up to 100, sorry about that.