Гриша и Дима играют в следующую игру: они разложили однокопеечные монетки в стопки (в разных стопках может быть различное количество монет), а стопки расположили на столе перед собой в ряд слева направо. Затем Гриша и Дима по очереди делают ходы. На каждом ходе один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается.

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

Формат входных данных:

Входной файл состоит из одной строки, в которой записаны: число стопок , за ним идут N чисел, задающих количество монет в стопках слева направо (количество монет в стопке — не менее 1 и не более 20000), а затем число K . Все числа в строке разделены пробелами.

Формат выходных данных:

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

Пример файлов входных и выходных данных:

stdin	stdout
3  4 9 1  3	14
4  1 2 2 7  3	5
5  3 4 8 1 7  2	18