感恩节的火鸡

你有听过农场主威廉与他的火鸡们的故事吗？威廉饲养的火鸡十分有趣，它们非常喜欢玩游戏，并且游戏的数量越多火鸡们长肉就会越多。威廉非常想让这批火鸡在感恩节前上市，但他又是个十分吝啬的家伙。威廉只打算在给定的预算内购入一些游戏平台和一些游戏，从而使他的火鸡们生产更多的肉。

威廉研究了N（1 <= N <= 50）种游戏平台，每一种游戏平台的价格是Pi（1 <= Pi <= 1000），并且每一种游戏平台有Gi（1 <= Gi <= 10）个只能在这种平台上运行的游戏。游戏厂商非常精明，你必须先买进一种游戏平台，才能买进在这种游戏平台上运行的游戏。每一个游戏有一个游戏的价格GPj（1 <= GPj <= 100），并且有一个产出值PVj（1 <= PVj<= 1000000），表示一只火鸡在玩这个游戏之后会长多少单位的肉。

假定威廉的预算为V（1 <= V <= 100000），即他最多可以花费的金钱。请帮助他确定应该买什么游戏平台和游戏，使得他能够获得的产出值的和最大。

例如：有3种游戏平台，并且预算V=800。

第一种游戏平台花费300并且有两个游戏。游戏1的价格为30，产出值为50。游戏2的价格为25，产出值为80。

第二种平台价格为600，并且只有一种游戏。游戏的花费为50，产出值为130。

第三种平台价格为400，并且有三种游戏。游戏1的价格为40，产出值为70。游戏2的价格为30，产出值为40。游戏3的价格为35，产出值为60。 威廉应该买第1和第3种平台，并且买平台1的游戏2，还有平台3的游戏1和游戏3。使得最后他最后的产出值最大，产出值为210: 输入格式 第1行: 两个由空格隔开的整数: N和V

第2到第N+1行: 第i+1行表示第i种游戏平台的价格和可以在这种游戏平台上面运行的游戏。包含: Pi, Gi还有Gi对由空格隔开的整数GPj, PVj

输出格式 一个整数，即威廉在预算内可以得到的最大的产出值。

输入/输出例子1 输入：

3 800

300 2 30 50 25 80

600 1 50 130

400 3 40 70 30 40 35 60

输出：

210