Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.
Входные данные
В первой строке находится сначала число стопок N, за ним идут N чисел, задающих количество монет в стопках слева направо, а затем число K. Все числа в строке разделены пробелами.
Ограничения: 1 <= N <= 180, 1 <= K <= 80, количество монет в стопке - не менее 1 и не более 20 000.
Выходные данные
Вывести одно число - максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 9 1 3
|
14
|
|
2
|
4 1 2 2 7 3
|
5
|
|
3
|
5 3 4 8 1 7 2
|
18
|