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

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

Фарфор находится на 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
Примечание

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

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