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$).

출력

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

제한

힌트