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

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

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

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

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

然后是 k_i 个整数 c_j，表示该堆硬币自顶向下每一枚硬币的面额。

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

【样例说明 1】

小图有 3 种方案：

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

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

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

【数据规模】

对于 40 \% 的数据， n \leq 8 ;

对于 100 \% 的数据， n \leq 100 ;

对于所有测试点，保证 1 \leq n \leq 100 , 1 \leq k_i \leq n ,1 \leq m \leq \sum{k_i}, 1 \leq c_j \leq 10^9 。

东方博宜OJ

背包问题动态规划