Правила новой телевизионной викторины следующие. В ряд расположены $$$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$$$).
Выведите одно число: какой максимальной выигрыш может гарантировать себе игрок.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
1 | 15 | $$$n \le 100$$$, $$$k = 2$$$, $$$a_i \le 10^5$$$ | |
2 | 14 | $$$n \le 100$$$ , $$$a_i \le 10^5$$$ | 1 |
3 | 15 | $$$n \le 5000$$$, $$$k = 2$$$, $$$a_i \le 10^5$$$ | 1 |
4 | 14 | $$$n \le 5000$$$, $$$a_i \le 10^5$$$ | 1–3 |
5 | 18 | $$$n \le 200\,000$$$, $$$k = 2$$$ | 1, 3 |
6 | 24 | $$$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$$$.