← 返回题目列表

Codeforces · 1442/D

D. 总和

中文机器翻译题面 查看原题

给你 $$$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