Есть $$$n$$$ неубывающих массивов из неотрицательных чисел.
Вася $$$k$$$ раз делает следующее:
Вася хочет максимизировать сумму чисел в своём кармане.
В первой строке находятся два целых числа $$$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$$$ действий.
3 3 2 5 10 3 1 2 3 2 1 20
26
Название |
---|