MEC '16 P3 - Getting Good at Programming

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Flowright wants to get good at programming. Programming is a game where you invest time to upgrade your skills. There are N skills, each with L_i 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. Flowright, being a passionate programmer, wants to maximize his experience earned in a given amount of time. In fact, as Flowright is very indecisive, he wants to know the maximum amount of experience he can gain in T amount of time.


1 \le N, T, L_i, x_{l_i} \le 100

1 \le t_{l_i} \le T

Input Specification

The first line of input will contain two integers, N and T. The next N lines will be in the format L_i\ t_1\ x_1\ t_2\ x_2 \dots t_{L-1}\ x_{L-1}\ t_L\ x_L.

L represents the number of levels for each skill. t and x represent the time needed to complete the level and the experience gained from completing the level, respectively.

Output Specification

A single integer for the maximum experience that Flowright 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


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.


  • 1
    minecraftyugi  commented on Oct. 18, 2017, 10:12 a.m.

    I'm probably misinterpreting the constraints, but the time for the levels exceeds the given max time for the last 2 test cases.