MEC '16 P3 - Getting Good at Programming - DMOJ: Modern Online Judge

MEC '16 P3 - Getting Good at Programming

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Authors:

Problem type

Flowright wants to get good at programming. Programming is a game where you invest time to upgrade your skills. There are $N$ $N$ skills, each with $L_i$ $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$ $T$ amount of time.

Constraints

$1 \le N, T, L_i, x_{l_i} \le 100$ $1 \leq N, T, L_{i}, x_{l_{i}} \leq 100$

$1 \le t_{l_i} \le T$ $1 \leq t_{l_{i}} \leq T$

Input Specification

The first line of input will contain two integers, $N$ $N$ and $T$ $T$ . The next $N$ $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_{i} t_{1} x_{1} t_{2} x_{2} \dots t_{L - 1} x_{L - 1} t_{L} x_{L}$ .

$L$ $L$ represents the number of levels for each skill. $t$ $t$ and $x$ $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

Copy

3 20
2 10 1 10 19
1 10 10
1 20 15

Sample Output

Copy

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

1

minecraftyugi commented on Oct. 18, 2017, 2:12 p.m.

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