B. Let Us Assemble a Portfolio Together
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

The [REDACTED] company is considering several projects to launch.

Each project can be launched in one of the several possible ways, or not launched at all.

The team of analysts has provided the expected costs and revenue for each possible launch way of each project.

The system is set up so that the costs are spent from a fixed budget that has been approved by the management in advance. At the same time, any revenue received does not increase the budget for starting other projects that have not yet been launched.

The management is only interested in the maximum total revenue. In other words, they are not interested in the total costs, except that they fit within the specified budget.

As a highly qualified specialist, you are asked to find the maximum total revenue.

Input

The first line contains two integers $$$n$$$ and $$$b$$$: the number of projects and the allocated budget ($$$1 \le n \le 20$$$, $$$0 \le b \le 10^9$$$).

Then, $$$n$$$ projects are listed, each on a new line. The description of the $$$i$$$-th project starts with a line containing an integer $$$k_i$$$: the number of possible launch ways for the project ($$$1 \le k_i \le 20$$$). Each of the next $$$k_i$$$ lines contains two integers $$$r_{ij}$$$ and $$$e_{ij}$$$: the revenue and costs, respectively, in the case of launching the $$$i$$$-th project in the $$$j$$$-th way ($$$0 \le r_{ij}, e_{ij} \le 10^9$$$).

The total number of all launch ways for all projects does not exceed $$$20$$$ ($$$\sum k_i \le 20$$$).

Output

Output a single integer $$$r$$$: the maximum total revenue.

Examples
Input
2 10
2
100 10
80 9
1
10 1
Output
100
Input
2 5
2
200 3
100 2
2
10 2
20 3
Output
210