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.wants to get good at programming. Programming is a game where you invest time to upgrade your skills. There are
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.
A single integer for the maximum experience thatcan gain in the given amount of time.
3 20 2 10 1 10 19 1 10 10 1 20 15
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.