27224번 - Викторина 다국어

Правила новой телевизионной викторины следующие. В ряд расположены $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$).

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

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

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