题目描述

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

威廉研究了 $N( 1 \le N \le 50 )$ 种游戏平台，每一种游戏平台的价格是 $P_i$ ( $1 \le P_i \le 1000$ )，并且每一种游戏平台有 $G_i(1 \le G_i \le 10 )$ 个只能在这种平台上运行的游戏。游戏厂商非常精明，你必须先买进一种游戏平台，才能买进在这种游戏平台上运行的游戏。每一个游戏有一个游戏的价格 $GP_j(1 \le GP_j \le 100$)，并且有一个产出值 $PV_j( 1 \le PV_j \le 1000000$)，表示一只火鸡在玩这个游戏之后会长多少单位的肉。

假定威廉的预算为 $V(1 \le V \le 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 种游戏平台的价格和可以在这种游戏平台上面运行的游戏。包含: $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