题目背景

$n$ 个货架，用二维数组表示价值，每个货架只能取出头部若干和尾部若干。取 $m$ 个物品价值之和最大多少？

题目描述

在发脾气时，蒻通常会砸碎一些珍藏的瓷器。每一声愤怒的尖叫都伴随着一件物品被砸碎。

瓷器收藏整齐地摆放在 $n$ 个架子上。每个架子上的物品都是一排排摆放的，因此人们只能拿取最外面的物品,即最左边或最右边的物品，而不能拿取架子中间的物品。一旦取走一件物品，就可以取走架子那一边的下一件物品。物品一旦被拿走，就不再放回货架。

你会得到所有物品的价值。你的任务是找出蒻的 $m$ 尖叫声对瓷器收藏造成的最大伤害。

输入格式

第一行输入数据包含两个整数 $n ( 1 ≤ n ≤ 100 )$ 和 $m ( 1 ≤ m ≤ 10000 )$。

接下来的 $n$ 行包含货架上物品的数值：

• 第一个数字表示该货架上物品的数量 $s_i(1\le s_i \le 100)$
• 接下来 $s_i$ 个整数表示物品的价值 $a_{i,j}(1\le a_{i,j} \le 100)$，按照它们在货架上出现的顺序排列(第一个数字对应最左边的物品，最后一个数字对应最右边的物品)。

输出格式

输出 $m$ 次尖叫的最大伤害。

输入输出样例 #1

输入 #1

2 3
3 3 7 2
3 4 1 5

输出 #1

15

输入输出样例 #2

输入 #2

1 3
4 4 3 1 2

输出 #2

9

说明/提示

对于$30\%$ 的数据：$1\le n\le 3,1\le s_i\le 10$

对于$60\%$ 的数据：$1\le n\le 10,1\le s_i\le 10$

对于$100\%$ 的数据：$1\le n\le 100,1\le s_i\le 100$