题目描述

刘老师准备为社团采购电子游戏设备，小珅和小泽负责整理大家的推荐。每款游戏都有一个体验评分，刘老师希望在预算内选择合适的设备和游戏。

同学们喜欢不同的游戏设备：小珅想用 Xbox 360 玩《光环 3》，小泽喜欢任天堂 Wii 上的《任天堂明星大乱斗》，还有同学想用 PlayStation 3 玩《合金装备 4》。刘老师可以购买若干游戏机（每种不超过一台）和游戏（每种不超过一款），但总花费不能超出预算。

刘老师调查了 $N$ 台游戏机，每台游戏机的价格为 $P_i$，以及独占发布于该游戏机的游戏数量 $G_i$。当然，同学们必须先拥有这台游戏机，才能购买该游戏机独占的任何游戏。每款游戏都有一个游戏价格 $GP_j$和一个生产值，在本次社团活动中表示这款游戏的体验评分。最后，刘老师有一个预算 $V$，这是他最多能花的钱。帮助他最大化他购买的游戏的生产值之和。

考虑一个例子，$N=3$ 台游戏机，预算 $V=800$ 美元。

第一台游戏机价格为 $300$ 美元，并有两个游戏，价格分别为 $30$ 美元和 $25$ 美元，生产值如下所示： | 游戏编号 | 价格 | 生产值 | |:-:|:-:|:-:| |$1$|$$30$|$50$| |$2$|$$25$|$80$|

第二台游戏机价格为 $600$ 美元，只有一个游戏： | 游戏编号 | 价格 | 生产值 | |:-:|:-:|:-:| |$1$|$$50$|$130$|

第三台游戏机价格为 $400$ 美元，有三个游戏： | 游戏编号 | 价格 | 生产值 | |:-:|:-:|:-:| |$1$|$$40$|$70$| |$2$|$$30$|$40$| |$3$|$$35$|$60$|

刘老师应该购买游戏机 $1$ 和 $3$，游戏机 $1$ 的游戏 $2$，以及游戏机 $3$ 的游戏 $1$ 和 $3$，以最大化他所购买游戏的生产值。该值为 210：

                                  生产值
        预算:      $800      
        游戏机 1  -$300
          游戏 2  -$25              80
        游戏机 3  -$400
          游戏 1  -$40              70
          游戏 3  -$35              60
      -------------------------------------------
        总计:        0 (>= 0)      210

输入格式

输入第 $1$ 行为两个用空格分隔的整数：$N$ 和 $V$

第 $2$ 到 $N+1$ 行：第 $i+1$ 行描述了游戏机 $i$ 的价格 $P_i$ 和其独占的游戏数量 $G_i$，接下来后面有 $G_i$ 对用空格分隔的整数 $GP_j$ 和 $PV_j$，描述其独占的各款游戏的信息。

输出格式

输出 $1$ 个整数，表示刘老师在他的预算内可以获得的最大生产值。

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

210

说明/提示

（由 ChatGPT 4o 进行翻译）

以下数据是本题实际评测数据的一部分。

1 1
17 6 38 755143 76 833438 8 875790 24 450145 84 785796 65 428440

0

2 7836
91 2 4 419240 76 620128
26 8 30 690769 70 165693 3 610862 39 838638 15 770378 22 695703 49 851844 68 90046

5753301

数据范围

$1 \leq N \leq 50$

$1 \leq P_i \leq 1000$

$1 \leq G_i \leq 10$

$1 \leq GP_j \leq 100$

$1 \leq PV_j \leq 1,000,000$

$1 \leq V \leq 100,000$