F2. Картинки с котиками (сложная версия)
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие простой версии от сложной — ограничения.

Вове очень нравятся картинки с котиками. Новостную ленту в социальной сети, в которой он сидит, можно представить как $$$n$$$ последовательных картинок (с котиками, конечно же). Все эти картинки нравятся Вове, но некоторые нравятся больше других: Вова оценивает красоту $$$i$$$-й картинки как $$$a_i$$$.

Вова хочет репостнуть ровно $$$x$$$ картинок так, что будут выполнены следующие условия:

  • для каждого отрезка новостной ленты из $$$k$$$ последовательных картинок Вова репостнет хотя бы одну из этих картинок;
  • сумма красот репостнутых картинок максимально возможна.

К примеру, если $$$k=1$$$, Вова хочет репостнуть все картинки. Если $$$k=2$$$, Вове не обязательно репостить все картинки, но для каждой пары соседних картинок хотя бы одна должна быть репостнута.

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

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

В первой строке заданы три числа $$$n, k$$$ и $$$x$$$ ($$$1 \le k, x \le n \le 5000$$$) — количество картинок в новостной ленте, минимальная длина подотрезка, на котором обязательно должна быть хотя бы одна репостнутая картинка, и количество картинок, которое собирается репостнуть Вова.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — красота $$$i$$$-й картинки.

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

Выведите -1, если нельзя выбрать картинки для репоста, чтобы выполнить условие задачи.

В противном случае выведите одно целое число — максимальную сумму красот репостнутых картинок при соблюдении всех условий.

Примеры
Входные данные
5 2 3
5 1 3 10 1
Выходные данные
18
Входные данные
6 1 5
10 30 30 70 10 10
Выходные данные
-1
Входные данные
4 3 1
1 100 1 1
Выходные данные
100