Video Game Troubles -vidgame

题目描述:

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

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

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

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

输入格式:

第 $1$ 行：两个由空格隔开的整数 $N$ 和 $V$ 。

第 $2$ 到第 $N+1$ 行：第$i+1$行表示第种游戏平台的价格和可以在这种游戏平台上面运行的游戏，包含$P_i,G_i$ 还有$G_i$ 对由空格隔开的整数$G{P}_j,P{V}_j$ 。

输出格式:

农夫约翰在预算内可以得到的最大的产出值。

样例输入:

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

样例输出:

210

时间限制: 1000ms
空间限制: 64MB

---

来源: Usaco2009 Dec Gold