Console Game Investment

Farmer John wants to maximize his cows' milk production by investing in game consoles and their exclusive games. He has researched (N) consoles (where (1 \le N \le 50)), each with a price (P_i) ((1 \le P_i \le 1000)) and (G_i) exclusive games ((1 \le G_i \le 10)). Each game for console (i) has a cost (GP_j) ((1 \le GP_j \le 100)) and a production value (PV_j) ((1 \le PV_j \le 10^6)), which represents how much milk it can help produce. Farmer John has a total budget (V) ((1 \le V \le 100000)). To buy any game for a particular console, he must first buy the console. Note that at most one unit of each console and each game is available.

The objective is to select a subset of consoles and, for each purchased console, a non-empty subset of its games such that the total cost (console prices plus game prices) does not exceed (V) and the total production value is maximized.

For example, consider the following dataset with (N=3) consoles and a budget (V=800):

Console 1: Price = 300; 2 games available:

• Game 1: Cost = 30, Production Value = 50
• Game 2: Cost = 25, Production Value = 80

Console 2: Price = 600; 1 game available:

• Game 1: Cost = 50, Production Value = 130

Console 3: Price = 400; 3 games available:

• Game 1: Cost = 40, Production Value = 70
• Game 2: Cost = 30, Production Value = 40
• Game 3: Cost = 35, Production Value = 60

The optimal choice is to buy Console 1 and Console 3, and then select Game 2 for Console 1, and Games 1 and 3 for Console 3, reaching a total production value of 210 under the budget.

The problem requires implementing an algorithm that correctly computes the maximum total production value under the budget constraint.

inputFormat

The input begins with a line containing two integers (N) and (V), the number of consoles and the total budget respectively. For each console (i) (1-based indexing), there is a line containing two integers: (P_i) (the price of console (i)) and (G_i) (the number of games for console (i)). This is followed by (G_i) lines, each containing two integers (GP_j) and (PV_j), representing the cost and production value of the (j^{th}) game for that console.

outputFormat

Output a single integer representing the maximum total production value that can be achieved given the budget constraint.

sample

3 800
300 2
30 50
25 80
600 1
50 130
400 3
40 70
30 40
35 60

210