E. Фарфор
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Во время истерик принцесса обычно бьет коллекционный фарфор. На один гневный вопль уходит один предмет.

Фарфор находится на n полках. На каждой полке предметы расставлены в один ряд так, что с полки можно брать только крайние предметы — либо крайний левый, либо крайний правый, но не предметы между ними. Когда предмет взят, открывается доступ к следующему предмету с этого края (см. пример). Если предмет взят, его уже нельзя вернуть на полки.

Задана ценность каждого предмета. Определите, во сколько обойдется хозяину коллекции принцессина истерика из m гневных воплей в худшем для него случае.

Входные данные

В первой строке входных данных записано два целых числа n (1 ≤ n ≤ 100) и m (1 ≤ m ≤ 10000). В следующих n строках заданы стоимости предметов на полках: первое число в строке — количество предметов на этой полке (целое число от 1 до 100, включительно), затем стоимости предметов (целые числа от 1 до 100, включительно) в том порядке, в каком они выставлены на полке (первый предмет ближе всего к левому краю полки, а последний предмет — к правому). Гарантируется, что общее количество предметов будет не менее m.

Выходные данные

Выведите максимальную стоимость истерики из m воплей.

Примеры
Входные данные
2 3
3 3 7 2
3 4 1 5
Выходные данные
15
Входные данные
1 3
4 4 3 1 2
Выходные данные
9
Примечание

В первом примере фарфор расставлен на двух полках, по три предмета на каждой. Чтобы получить наибольшую сумму стоимостей, можно взять два предмета с левого края первой полки и один с правого края второй.

Во втором примере полка всего одна, и выбора нет: все три предмета берутся с нее — два с левого края и один с правого.