## MEC '16 P3 - Getting Good at Programming

View as PDF

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 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. 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 amount of time.

#### Input Specification

The first line of input will contain two integers, and . The next lines will be in the format .

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

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.