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.

Constraints

~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

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.