Однокопійчані монетки разкладено у стопки (у стопках може бути різна кількість монет), а стопки поставлено на столі у ряд зліва направо. Двоє супротивників по черзі роблять ход. Хід полягає у тому, що один з гравців бере зліва декілька стопок підряд, не менше однієї, але і не більше, ніж перед цим взяв його супротивник. Перший гравець своїм першим ходом бере не більше \textbf{K} стопок. Гра закінчується, коли стопок не залишається. Потрібно знайти максимальне число монет, які може отримати перший участник після завершення гри, якщо другий гравець також намагається ходити так, щоб отримати якомога більше монет. \InputFile У першому рядку знаходиться спочатку число стопок \textbf{N}, за ним йде \textbf{N} чисел, що задають кількості монет у стопках зліва направо, а потім число \textbf{K}. Всі числа у рядку відокремлені пропусками. \textbf{1} <= \textbf{N} <= \textbf{180}, \textbf{1} <= \textbf{K} <= \textbf{80}, кількість монет у стопці - не менше \textbf{1} і не більше \textbf{20 000}. \OutputFile Вивести одне число - максимальну кількість монет, яку завідомо може отримати перший гравець.