You are given $$$n$$$ non-decreasing arrays of non-negative numbers.
Vasya repeats the following operation $$$k$$$ times:
Vasya wants to maximize the sum of the elements in his pocket.
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$$$.
Print one integer: the maximum possible sum of all elements in Vasya's pocket after $$$k$$$ operations.
3 3 2 5 10 3 1 2 3 2 1 20
26
Name |
---|