[USACO09DEC]Video Game Troubles G

题面翻译

农夫约翰的奶牛们打游戏上瘾了！本来约翰是想要按照调教兽的做法拿她们去电击戒瘾的，可后来他发现奶牛们玩游戏之后比原先产更多的奶。很明显，这是因为满足的牛会产更多的奶。

但是，奶牛们因何者为最好的游戏主机而吵得不可开交。约翰想要在给定的预算内购入一些游戏平台和一些游戏，使他的奶牛们生产最多的奶牛以养育最多的小牛。

约翰考察了 $N$ 种游戏主机，第 $i$ 种主机的价格是 $P_i$，该主机有 $G_i$ 个独占游戏。很明显，奶牛必须先买进一种游戏主机，才能买进在这种主机上运行的游戏。在每种主机中，游戏 $j$ 的价格为 $\mathit{GP}_j$，每头奶牛在玩了该游戏后的牛奶产量为 $\mathit{PV}_j$。

农夫约翰的预算为 $V$。请帮助他确定应该买什么游戏主机和游戏，使得他能够获得的产出值的和最大。

样例说明 1

假设 现在有 $N=3$ 种主机，预算为 $V=800$。第一种主机的售价为 $300$，并且有两款游戏：

第二种主机的售价为 $600$，并且只有一款游戏：

第二种主机的售价为 $400$，并且有三款游戏：

理想方案：

产量
           预算:    $800      
           主机 1  -$300
           游戏 2   -$25       80
           主机 3  -$400
           游戏 1   -$40       70
           游戏 3   -$35       60
      -------------------------------------------
          总和：   0 (≥ 0)     210

输入格式

第1行包含两个整数N和V，代表有N种主机，约翰的预算为V。

从第2~N+1行，第i+1行首先包含了一个整数为主机价格Pi，接下来有一个整数Gi代表该主机上的游戏数量，接下来包含Gi对数字，每一对数字代表第i台主机的第j款游戏的价格GPj和奶牛玩游戏之后的产奶量PVj。

输出格式

输出一个整数，为约翰在预算内能获得的牛奶产出值的最大和。

样例 #1

样例输入 #1

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

样例输出 #1

210

数据规模

1<=N<=50，1<=V<=100000，1<=Gi<=10，1<=GPj<=100，1<=PVj<=1000000。