Porcelain

题意： 有一个公主一生气就喜欢摔东西。现在有很多个柜子，每个柜子里面装着很多物品，公主每次摔东西只能随机的选择一个柜子，拿出最左边或者最右边的一个物品摔碎，给出公主最多生气的次数m，求生完气之后，公主摔掉物品的价值的最大总和。 输入： 第一行输入n(1<=n<=100),m(1<=m<=10000),n为柜子的层数，m为公主最多生气的次数m。 接下来n行，每行第一个输入该层物品的数量k(1<=k<=100),接下来输入k个物品的价值v[i]。 输出： 输出所扔物品的最大价值 By @AlphaGo fix by @烈酒诱鹿

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.

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 $ .

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

2 3
3 3 7 2
3 4 1 5

15

1 3
4 4 3 1 2

9

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.