时间限制：1秒　　内存限制：256M

---

【题目描述】

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

　　但是，奶牛们在哪个才是最好的游戏平台这个问题上产生了巨大的分歧。一只奶牛 想要买一台Xbox 360来跑《光晕3》；另外一只奶牛想要一台任天堂Wii来跑《任天堂明星大乱斗X》；第三只奶牛想要在PlayStation 3上面玩《潜龙谍影4》，顺便还能看某些高画质的日本电影。FJ想要在给定的预算内购入一些游戏平台和一些游戏，使他的奶牛们生产最多的奶牛以养育最多的孩子。

　　FJ研究了 \(N\) 种游戏平台，每一种游戏平台的价格是 \(P_i\)，并且每一种游戏平台有 \(G_i\) 个只能在这种平台上运行的游戏。很明显，奶牛必须先买进一种游戏平台，才能买进在这种游戏平台上运行的游戏。每一个游戏有一个游戏的价格 \(GP_i\) 并且有一个产出值 \(PV_j\)，表示一只牛在玩这个游戏之后会产出多少牛奶。最后，农夫约翰的预算为V，即他最多可以花费的金钱。请帮助他确定应该买什么游戏平台和游戏，使得他能够获得的产出值的和最大。

　　考虑下面的数据，有 \(N\) 种游戏平台，并且有 \(V=\)800元 预算。第一种游戏平台花费 300 并且有两个游戏，价格分别为和 25，它们的产出值如下所示:

　　第二种平台价格为 600 元，并且只有一种游戏:

　　第三种平台价格为 400 元，并且有三种游戏:

　　农夫约翰应该买第 1 和第 3 种平台，并且买平台 1 的游戏 2，还有平台 3 的游戏 1 和游戏 3。使得最后他最后的产出值最大，为 210：

【输入格式】

　　第 1 行: 两个由空格隔开的整数: \(N\) 和 \(V\)。
　　第 2 到第 \(N+1\) 行: 第 \(i+1\) 行表示第 \(i\) 种游戏平台的价格和可以在这种游戏平台上面运行的游戏。包含: \(P_i（1≤P_i≤1000）\)，\(G_i（1≤G_i≤10）\)还有 \(G_i\) 对由空格隔开的整数 \(GP_j, PV_j（1≤GP_j≤100、1≤PV_j≤1000000）\)。

【输出格式】

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

【输入输出样例】

　Input

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

　Output

210

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤50\)，\(1≤V≤100000\)。

【来源】

　　Mr.he