CF1442D.Sum

You are given $n$ non-decreasing arrays of non-negative numbers.

Vasya repeats the following operation $k$ times:

• Selects a non-empty array.
• Puts the first element of the selected array in his pocket.
• Removes the first element from the selected array.

Vasya wants to maximize the sum of the elements in his pocket.

给你 $n$ 个非负数构成的非递减数组。

瓦夏重复以下操作 $k$ 次：

• 选择一个非空数组；
• 将所选数组的第一个元素放入他的口袋；
• 从所选数组中删除第一个元素。

瓦夏希望使他口袋中所有元素的和最大。

The first line contains two integers $n$ and $k$ ($1 \le n, k \le 3\,000$): the number of arrays and operations.

Each of the next $n$ lines contain an array. The first integer in each line is $t_i$ ($1 \le t_i \le 10^6$): the size of the $i$-th array. The following $t_i$ integers $a_{i, j}$ ($0 \le a_{i, 1} \le \ldots \le a_{i, t_i} \le 10^8$) are the elements of the $i$-th array.

It is guaranteed that $k \le \sum\limits_{i=1}^n t_i \le 10^6$.

第一行包含两个整数 $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$）为该数组的元素。

保证 $k \le \sum\limits_{i=1}^n t_i \le 10^6$。

Print one integer: the maximum possible sum of all elements in Vasya's pocket after $k$ operations.

输出一个整数：经过 $k$ 次操作后，瓦夏口袋中所有元素之和的最大可能值。