题目描述

公主发脾气时通常会摔碎一些可收藏的瓷器。每次愤怒的尖叫都伴随着摔碎一个物品。

瓷器摆放整齐地放在 $n$ 个架子上。在每个架子上，物品都是一排排放的，因此只能访问最外侧的物品 —— 最左边或最右边的物品，而不能访问中间的物品。一旦取走一个物品，就可以访问该侧的下一个物品（参见示例）。一旦取走一个物品，就不能把它放回架子上。

给定所有物品的价值。你的任务是找出公主 $m$ 次尖叫后对瓷器收藏可能造成的最大破坏。

输入格式

输入数据的第一行包含两个整数 $n$（$1 \le n \le 100$）和 $m$（$1 \le m \le 10000$）。

接下来的 $n$ 行包含架子上物品的价值：第一个数字给出了这个架子上的物品数量（介于 $1$ 和 $100$之间的整数），然后是物品的价值（介于 $1$ 和 $100$ 之间的整数），按照它们在架子上出现的顺序排列（第一个数字对应最左边的物品，最后一个数字对应最右边的物品）。物品的总数保证至少为 $m$。

输出格式

输出 $m$ 次尖叫后可能造成的最大总价值。

样例

2 3
3 3 7 2
3 4 1 5

15

1 3
4 4 3 1 2

9

说明/提示

样例解释

在第一个样例中，有两个架子，每个架子上有三个物品。为了最大化所选物品的总价值，可以从第一个架子的左侧取两个物品，从第二个架子的右侧取一个物品。

在第二个样例中，只有一个架子，因此从中取走所有三个物品 —— 两个从左侧取，一个从右侧取。