Statement is not available in English language
J. Выбор чисел 3
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность $$$A$$$ из $$$n$$$ целых чисел. Вам нужно выбрать из нее $$$k$$$ чисел, так, чтобы между выбранными числами было расстояние хотя бы $$$d$$$, а сумма выбранных чисел была максимальна. Это - самая сложная версия задачи, и в ней $$$k$$$ произвольно, а ограничение на $$$n$$$ больше, чем в простой версии. Расстояние между элементами последовательности с номерами $$$i, j$$$ равно $$$|i - j|$$$.

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

В первой строке вам дано число $$$1 \le n \le 150000$$$, число $$$3 \le k \le min(50, n)$$$ и число $$$1 \le d \le n$$$. Выполняется ограничение $$$(k - 1) * d + 1 \le n$$$, которое означает, что вы можете точно взять $$$k$$$ чисел по описанным правилам из последовательности. В следующей строке вам дана последовательность $$$A$$$ – $$$n$$$ целых чисел $$$-10^9 \le a_i \le 10^9$$$.

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

Выведите ответ на задачу – максимальную сумму выбранных чисел.

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