28516번 - Уборка листьев 다국어

В задаче C вы могли узнать о последствиях уборки двора Евстиграфа, однако кому-то может быть интереснее узнать о процессе, чем о результате.

Во время уборки одной из основных проблем было собрать упавшие на землю листья в кучи так, чтобы Евстиграф был доволен результатом. Всего в итоге собрали $n$ кучек листьев, в $i$-й из которых получилось ровно $a_i$ листьев, после чего их показали Евстиграфу.

Евстиграф решил, что не хочет тратить время на проверку всех кучек, и будет оценивать проделанную работу следующим критерием:

1. сначала он попросит вас назвать непрерывный отрезок из ровно $k$ целых чисел, то есть некоторый $[l, r]$, что $r - l + 1 = k$;
2. затем он посчитает сумму размеров кучек, которые попадают в этот отрезок, то есть $S = \sum\limits_{l \leqslant a_i \leqslant r} 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$ \ldots $a_n$ --- размеры кучек листьев ($1 \leqslant a_i \leqslant 10^9$).

Выведите одно число --- минимальное возможное значение описанной суммы.