CF148E.Porcelain

During her tantrums the princess usually smashes some collectable porcelain. Every furious shriek is accompanied with one item smashed.

The collection of porcelain is arranged neatly on n shelves. Within each shelf the items are placed in one row, so that one can access only the outermost items — the leftmost or the rightmost item, not the ones in the middle of the shelf. Once an item is taken, the next item on that side of the shelf can be accessed (see example). Once an item is taken, it can't be returned to the shelves.

You are given the values of all items. Your task is to find the maximal damage the princess' tantrum of m shrieks can inflict on the collection of porcelain.

在公主发脾气时，她通常会砸碎一些收藏的瓷器。每次愤怒的尖叫都会伴随着一件瓷器被砸碎。

这些瓷器整齐地摆放在 $n$ 个架子上。每个架子上的瓷器排成一行，因此只能取到最外侧的瓷器——即最左边或最右边的瓷器，而无法直接取到架子中间的瓷器（见示例）。一旦从某侧取走一件瓷器，该侧下一个紧邻的瓷器便变得可取（见示例）。已取出的瓷器不能再放回架子上。

你将获得所有瓷器的价值。你的任务是：求出公主在连续 $m$ 次尖叫所引发的暴怒中，最多能对瓷器收藏造成多大的破坏（即所砸碎瓷器的总价值最大值）。

The first line of input data contains two integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 10000). The next n lines contain the values of the items on the shelves: the first number gives the number of items on this shelf (an integer between 1 and 100, inclusive), followed by the values of the items (integers between 1 and 100, inclusive), in the order in which they appear on the shelf (the first number corresponds to the leftmost item, the last one — to the rightmost one). The total number of items is guaranteed to be at least m.

输入数据的第一行包含两个整数 $n$（$1 \leq n \leq 100$）和 $m$（$1 \leq m \leq 10000$）。接下来的 $n$ 行描述货架上物品的价值：每行第一个数字表示该货架上的物品数量（一个介于 $1$ 到 $100$ 之间的整数），随后是这些物品的价值（均为介于 $1$ 到 $100$ 之间的整数），按其在货架上的从左到右顺序给出（第一个数字对应最左侧的物品，最后一个数字对应最右侧的物品）。保证物品总数至少为 $m$。

Output the maximal total value of a tantrum of m shrieks.

输出由 m 次尖叫组成的暴怒（tantrum）的最大总价值。

In the first case there are two shelves, each with three items. To maximize the total value of the items chosen, one can take two items from the left side of the first shelf and one item from the right side of the second shelf.

In the second case there is only one shelf, so all three items are taken from it — two from the left side and one from the right side.

第一种情况中有两个书架，每个书架上有三件物品。为使所选物品的总价值最大化，可以从第一个书架的左侧取两件物品，并从第二个书架的右侧取一件物品。

第二种情况中只有一个书架，因此全部三件物品均取自该书架——其中两件来自左侧，一件来自右侧。