题目描述 有 n 堆硬币，每堆硬币都上下叠在一起，形成类似“栈”的结构。

小图可以拿走至多 m 枚硬币，但对于某堆硬币，他只能拿走位于最顶部的若干枚，而不允许从下面抽出。

问在最优决策下，小图能拿走的硬币的最大总面额是多少？

输入格式 第一行两个整数 n , m ,表示硬币堆数与可以取走的硬币数量。

接下来 n 行，每行首先有一个整数 K[i] ，表示第i堆硬币的数量。

然后是 K[i] 个整数 C[i][j] ,表示该堆硬币自顶向下每一枚硬币的面额。

输出格式 输出一行，一个整数，表示小图能拿到的最大总面额。

样例

样例输入 1 2 2

3 1 100 3

3 7 8 9

样例输出 1:101

样例说明 1

小图有3种方案：

只在第一堆拿：1+100=101

只在第二堆拿：7+8=15

两堆各拿一枚：1+7=8

样例输入 2:

7 7

1 100

1 100

1 100

1 100

1 100

1 100

//原题见(oj.turingedu.cn/class/148/lesson/14/problem/) 用户名可用liguoguo，密码123456