给你 $$$n$$$ 非递减非负数数组。
Vasya 重复以下操作 $$$k$$$ 次:
- 选择非空数组。
- 将所选数组的第一个元素放入他的口袋中。
- 从所选数组中删除第一个元素。
Vasya 想要最大化他口袋里元素的总和。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 3\,000$$$):数组和操作的数量。
接下来的 $$$n$$$ 行都包含一个数组。每行的第一个整数是 $$$t_i$$$ ($$$1 \le t_i \le 10^6$$$):第 $$$i$$$ 数组的大小。以下 $$$t_i$$$ 整数 $$$a_{i, j}$$$ ($$$0 \le a_{i, 1} \le \ldots \le a_{i, t_i} \le 10^8$$$) 是第 $$$i$$$ 数组的元素。
保证 $$$k \le \sum\limits_{i=1}^n t_i \le 10^6$$$。
输出
打印一个整数:$$$k$$$ 运算后 Vasya 口袋中所有元素的最大可能总和。
示例
输入 #1
3 3 2 5 10 3 1 2 3 2 1 20
输出 #1
26