MEC '16 P3 - Getting Good at Programming

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.

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. Where L represents the number of levels for each skill and t and x represent the time needed to complete the level and the experience gained from completing the level, respectively.


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

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.

  • 2
    Zander  commented on March 25, 2016, 5:09 p.m.

    I think it goes higher than 10

    • 3
      Hypnova  commented on March 25, 2016, 5:22 p.m.

      Yes it goes up to 100, sorry about that.