Orange的管道II

题目描述

上回说到，Orange有一根长长的里面装有小球的管道，他可以将管道左右两端的小球取出来，减轻管道的重量，以方便他将管道搬到另一个地方。由于上次Orange搬运管道任务完成的十分出色(其实是偷懒)，毕老师这一次让Orange再次将 $n$ 根装有小球的管道搬到另一个地方去。

Orange十分开心(不愿)地接下了这个任务，为了继续偷懒，他这次也可以从任意一根管道的左右两端偷偷拿走一些小球，以减轻搬运的重量，同时，为了防止被毕老师发现端倪，他最多只能拿走 $m$ 个小球。

Orange想知道，他最多可以减轻多少重量呢？换句话说，你可以进行 $m$ 次如下操作: 从 $n$ 个管道的任意一个管道的两端取走一个小球(只能取两端的)，你需要最大化你拿出小球的总质量。

输入格式

输入共包含 $2n+1$ 行，其中第一行包含两个整数 $n(n\leq100)$ 和 $m(\leq10000)$，接下来的 $2n$ 行中，每两行用于表示一根管道，第一行包含一个整数 $c_i(c_i\leq100)$，代表第 $i$ 根管道中小球的数量，第二行包含 $c_i$ 个整数 $w_{ij}$，表示第 $i$ 根管道中第 $j$ 个小球的质量。

同时题目保证: $\sum c_i \geq m$。

输出格式

一个整数，表示Orange最多可以减轻的重量。

样例 #1

样例输入 #1

2 3
3 
3 7 2
3 
4 1 5

样例输出 #1

15

提示

可以从管道1中拿去3和7，再从管道2中拿去5，可以证明这是最优拿法。