|
Игра с монетами
(Время: 1 сек. Память: 16 Мб Сложность: 47%)
Гриша и Дима играют в следующую игру: они разложили однокопеечные монетки в стопки (в разных стопках может быть различное количество монет), а стопки расположили на столе перед собой в ряд слева направо. Затем Гриша и Дима по очереди делают ходы. На каждом ходе один из игроков берет слева несколько стопок, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается.
Требуется написать программу, позволяющую вычислить, какое максимальное число монет может получить первый участник после окончания игры, если второй – тоже старается ходить так, чтобы получить как можно больше монет.
Входные данные
Входной файл INPUT.TXT состоит из одной строки, в которой записаны: число стопок N (1 ≤ N ≤ 180), за ним идут N чисел, задающих количество монет в стопках слева направо (количество монет в стопке – не менее 1 и не более 20000), а затем число K, ограничивающее количество стопок, которые первый игрок может взять на первом ходе (1 ≤ K ≤ 80). Все числа в строке разделены пробелом.
Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести одно число – максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 4 9 1 3 | 14 |
| 2 | 4 1 2 2 7 3 | 5 |
| 3 | 5 3 4 8 1 7 2 | 18 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
