В задаче C вы могли узнать о последствиях уборки двора Евстиграфа, однако кому-то может быть интереснее узнать о процессе, чем о результате.
Во время уборки одной из основных проблем было собрать упавшие на землю листья в кучи так, чтобы Евстиграф был доволен результатом. Всего в итоге собрали $$$n$$$ кучек листьев, в $$$i$$$-й из которых получилось ровно $$$a_i$$$ листьев, после чего их показали Евстиграфу.
Евстиграф решил, что не хочет тратить время на проверку всех кучек, и будет оценивать проделанную работу следующим критерием:
Евстиграф считает, что уборка была выполнена тем качественнее, чем меньше значение получившейся суммы $$$S$$$. Помогите людям, которые занимались уборкой, выбрать такие $$$l$$$ и $$$r$$$, для которых получившаяся $$$S$$$ будет минимальна. Разумеется, выбирать отрицательные или слишком большие $$$l$$$ и $$$r$$$ нельзя, поэтому должно выполняться $$$1 \leqslant l \leqslant r \leqslant c$$$ для заранее заданного $$$c$$$.
В первой строке через пробел даны три целых числа $$$n$$$, $$$c$$$ и $$$k$$$ — количество кучек, ограничение сверху на выбираемый отрезок и длина отрезка соответственно ($$$1 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant k \leqslant c \leqslant 10^9$$$).
Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$ ... $$$a_n$$$ — размеры кучек листьев ($$$1 \leqslant a_i \leqslant 10^9$$$).
Выведите одно число — минимальное возможное значение описанной суммы.
5 10 6 1 3 5 2 4
5
5 10 5 5 3 4 1 2
0
5 6 2 5 3 1 4 2
3
3 10 5 1 2 7
2