410156: GYM103965 J Уборка листьев

J. Уборка листьевограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

В задаче 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$$$ ... $$$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