Putata 正在准备由国际计算机游戏公司 (ICPC) 举办的 RPG 职业联赛 (RPL)。在这个 RPG 游戏中，玩家可以同时穿戴 $n$ 件装备。每件装备都能为玩家提供一定的基础战力。游戏中存在一个魔法增益效果，可以升级每件装备，使其提供额外的奖励战力。

然而，该增益效果是有限的，它最多只能增益 $k$ 点战力。形式化地讲，假设玩家初始时未穿戴任何装备，随后将依次穿戴这 $n$ 件装备。游戏服务器会根据玩家穿戴装备的顺序，依次扫描这 $n$ 件装备。当服务器扫描第 $i$ 件装备时（该装备的基础战力为 $p_i$），令 $sum = \sum_{1 \le j < i} p_j$ 表示之前已扫描装备的总战力：

• 如果 $sum + p_i \le k$，则整件装备都会被升级。该增益将提供 $w_{i, p_i}$ 点奖励战力。
• 如果 $sum \ge k$，则该装备不会被升级。该增益将不提供任何奖励。
• 否则，只有该装备的一部分会被升级。该增益将提供 $w_{i, k-sum}$ 点奖励战力。

Putata 很聪明，他很快意识到可以通过调整穿戴这 $n$ 件装备的顺序来获得更多的奖励战力！遗憾的是，Putata 不知道最优的穿戴顺序，请编写一个程序来帮助他。

游戏服务器执行的魔法增益行为是一个 bug。游戏代码能运行全靠这些 bug，因此可能存在 $a < b$ 但 $w_{i, a} > w_{i, b}$ 的情况。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 3\,000, 0 \le k \le 3\,000$)，分别表示装备的数量和限制 $k$。

接下来的 $n$ 行，每行首先输入一个整数 $p_i$ ($1 \le p_i \le 10$)，表示第 $i$ 件装备的基础战力，随后输入 $p_i$ 个整数 $w_{i, 1}, w_{i, 2}, \dots, w_{i, p_i}$ ($1 \le w_{i, j} \le 10^5$)。

输出格式

输出一行，包含一个整数，表示所能达到的最大总奖励战力。基础战力不计入答案。

样例

输入 1

4 5
2 1 3
2 1 1
2 3 1
2 1 3

输出 1

9