Во время истерик принцесса обычно бьет коллекционный фарфор. На один гневный вопль уходит один предмет.
Фарфор находится на n полках. На каждой полке предметы расставлены в один ряд так, что с полки можно брать только крайние предметы — либо крайний левый, либо крайний правый, но не предметы между ними. Когда предмет взят, открывается доступ к следующему предмету с этого края (см. пример). Если предмет взят, его уже нельзя вернуть на полки.
Задана ценность каждого предмета. Определите, во сколько обойдется хозяину коллекции принцессина истерика из m гневных воплей в худшем для него случае.
Выходные данные
Выведите максимальную стоимость истерики из m воплей.
Примечание
В первом примере фарфор расставлен на двух полках, по три предмета на каждой. Чтобы получить наибольшую сумму стоимостей, можно взять два предмета с левого края первой полки и один с правого края второй.
Во втором примере полка всего одна, и выбора нет: все три предмета берутся с нее — два с левого края и один с правого.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
3 3 7 2
3 4 1 5
|
15
|
|
2
|
1 3
4 4 3 1 2
|
9
|