Викторина
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Правила новой телевизионной викторины следующие. В ряд расположены $$$n$$$ ячеек, пронумерованных от $$$1$$$ до $$$n$$$, в $$$i$$$-й ячейке находится $$$a_i$$$ монет.

Игрок может выбрать целое число $$$b$$$ и заплатить $$$b$$$ монет. Тогда ведущий забирает монеты из всех ячеек, где лежит не более $$$b$$$ монет, соответствующие ячейки становятся пустыми. После этого среди любых $$$k$$$ подряд идущих ячеек должно быть не менее $$$m$$$ пустых. После этого игрок забирает все оставшиеся на поле монеты, если он забрал $$$a$$$ монет, его выигрыш составит $$$a-b$$$ монет.

Помогите игроку понять, какое максимальный выигрыш он может гарантировать.

Входные данные

На первой строке ввода находятся целые числа $$$n$$$, $$$k$$$ и $$$m$$$ ($$$1 \le m < k \le n \le 200\,000$$$).

На второй строке находятся $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$).

Выходные данные

Выведите одно число: какой максимальной выигрыш может гарантировать себе игрок.

Система оценки

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

ПодзадачаБаллыДоп. ограниченияНеобх. подзадачи
115$$$n \le 100$$$, $$$k = 2$$$, $$$a_i \le 10^5$$$ 
214$$$n \le 100$$$ , $$$a_i \le 10^5$$$1
315$$$n \le 5000$$$, $$$k = 2$$$, $$$a_i \le 10^5$$$1
414$$$n \le 5000$$$, $$$a_i \le 10^5$$$1–3
518$$$n \le 200\,000$$$, $$$k = 2$$$1, 3
624$$$n \le 200\,000$$$1–5

Примеры

Входные данные
8 4 2
3 7 4 1 5 9 2 6
Выходные данные
17
Входные данные
5 2 1
2 2 2 2 2
Выходные данные
-2

Примечание

В первом примере игрок выбирет $$$b = 5$$$. После удаления монет из ячеек, в которых лежит не более чем по $$$5$$$ монет, количество монет в ячейках оказывается равно $$$[0, 7, 0, 0, 0, 9, 0, 6]$$$, суммарно он забирает из ячеек $$$22$$$ монеты, с учетом ранее отданных $$$5$$$ монет выигрыш игрока составляет $$$17$$$ монет.

Во втором примере, чтобы добиться, чтобы среди любых двух подряд идущих ячеек была хотя бы одна пустая, игроку приходится выбрать $$$b = 2$$$. После этого монет в ячейках нет, и выигрыш игрока оказывается отрицательным: $$$-2$$$.