Единственное отличие простой версии от сложной — ограничения.
Вове очень нравятся картинки с котиками. Новостную ленту в социальной сети, в которой он сидит, можно представить как \(n\) последовательных картинок (с котиками, конечно же). Все эти картинки нравятся Вове, но некоторые нравятся больше других: Вова оценивает красоту \(i\)-й картинки как \(a_i\).
Вова хочет репостнуть ровно \(x\) картинок так, что будут выполнены следующие условия:
- для каждого отрезка новостной ленты из \(k\) последовательных картинок Вова репостнет хотя бы одну из этих картинок;
- сумма красот репостнутых картинок максимально возможна.
К примеру, если \(k=1\), Вова хочет репостнуть все картинки. Если \(k=2\), Вове не обязательно репостить все картинки, но для каждой пары соседних картинок хотя бы одна должна быть репостнута.
Помогите Вове подсчитать, возможно ли таким образом выбрать картинки, которые он репостнет, и если это возможно, какой максимальной суммарной красоты репостнутых картинок можно добиться.
Выходные данные
Выведите -1, если нельзя выбрать картинки для репоста, чтобы выполнить условие задачи.
В противном случае выведите одно целое число — максимальную сумму красот репостнутых картинок при соблюдении всех условий.