D. Сумма
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$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