J17 习题-9 奶牛玩游戏

题目描述

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

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

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

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

输入格式

第一行$2$个整数，$N,V$，代表有 $N$ 种主机，约翰的预算为 $V$ ；

接下来 $N$ 行，每行首先有一个整数，表示 $P_i$，然后有一个整数 $G_i$ 表示该主机上的游戏数量，接下来包含 $G_i$ 对数字，每一对数字代表第 $i$ 台主机的第 $j$ 款游戏的价格 $GP_j$ 和 奶牛玩了这款游戏后的产奶量 $PV_j$ 。

输出格式

一个非负整数，表示最大产奶量的和。

样例输入

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

样例输出

210

数据范围

$100\%$ 的数据：$1 \leq N\leq 50$ , $1 \le V \le 100000$， $1\le G_i \le 10$，$1 \le GP_j \le 100$，$1 \le PV_j \le 1000000$。