낙엽 치우기

C번 문제에서 에브스티그라프 마당 청소의 결과를 다루었습니다. 이 문제는 결과보다 과정이 궁금한 분들을 위한 것입니다.

청소 중 가장 큰 문제는 땅에 떨어진 낙엽을 에브스티그라프가 만족할 만한 더미로 모으는 것이었습니다. 최종적으로 $n$개의 낙엽 더미를 모았고, $i$번째 더미에는 정확히 $a_i$개의 낙엽이 있습니다. 이후 더미들을 에브스티그라프에게 보여 주었습니다.

에브스티그라프는 모든 더미를 확인하는 데 시간을 쓰고 싶지 않아서 다음 기준으로 작업을 평가합니다.

1. 먼저 연속된 정수 $k$개로 이루어진 구간을 말해 달라고 요청합니다. 즉, $r - l + 1 = k$를 만족하는 $[l, r]$을 고릅니다.
2. 그다음 크기가 $l$ 이상 $r$ 이하인 더미들의 크기를 모두 더한 합 $S = \sum_{l \leqslant a_i \leqslant r} a_i$를 계산합니다.

합 $S$가 작을수록 청소가 잘 된 것으로 봅니다. 청소를 맡은 사람들이 $S$가 최소가 되도록 $l$과 $r$을 고를 수 있게 도와주세요. 다만 $l$과 $r$은 음수이거나 지나치게 클 수 없으며, 주어진 $c$에 대해 $1 \leqslant l \leqslant r \leqslant 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$)

위에서 정의한 합의 최솟값을 한 줄에 출력합니다.