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 \) 对由空格隔开的整数\( 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

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

---

来源: Usaco2009 Dec Gold