Codeforces Round 105 (Div. 2) |
---|
Закончено |
Во время истерик принцесса обычно бьет коллекционный фарфор. На один гневный вопль уходит один предмет.
Фарфор находится на 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
В первом примере фарфор расставлен на двух полках, по три предмета на каждой. Чтобы получить наибольшую сумму стоимостей, можно взять два предмета с левого края первой полки и один с правого края второй.
Во втором примере полка всего одна, и выбора нет: все три предмета берутся с нее — два с левого края и один с правого.
Название |
---|