Rikka와 RCPC

시간 제한1초메모리 제한512 MB

요약

앞의 K일을 모두 무시한 날에만 공격 없이 답할 수 있을 때, 답할 날을 골라 총 공격량을 최소화합니다.

문제

Rikka는 전 세계 대회인 RCPC(Rikka's collegiate programming contest)를 개최할 예정이다.

대회 준비에는 $n$ 일이 걸린다. 그동안 RCPC 공식 QQ 그룹에는 참가자, 코치, 그리고 멜론을 먹는 사람들까지 많은 질문을 올린다. Rikka는 $n$ 일 중 일부 날에는 QQ 그룹을 무시하기로 했다.

하지만 질문을 계속 무시하면 참가자들이 화를 낼 수 있다. 1일차가 시작되기 전 참가자들의 분노 수치 $A$ 는 $0$ 이다. $i$ 일차가 시작될 때 분노 수치는 $a_i$ 만큼 증가한다. 그다음은 다음과 같다.

$A$ 가 기준값 $T$ 보다 엄격하게 크면 참가자들은 매우 화가 나고, Rikka는 $2A$ 의 공격을 받는다. 그날이 끝날 때 $A$ 는 $0$ 으로 초기화된다.
$A$ 가 $T$ 이하이고 Rikka가 질문을 무시하기로 하면 그날은 아무 일도 일어나지 않는다.
$A$ 가 $T$ 이하이고 Rikka가 질문에 답하기로 했는데, 이전 $K$ 일 동안, 즉 $i-K$ 일차부터 $i-1$ 일차까지 질문을 모두 무시했다면 참가자들은 Rikka의 어려움을 알아준다. Rikka는 공격을 받지 않고, 그날이 끝날 때 $A$ 는 $0$ 으로 초기화된다.
그 외의 경우, Rikka가 질문에 답하더라도 참가자들은 답변이 너무 느리다고 Rikka를 탓하며, Rikka는 $A$ 의 공격을 받는다. 그날이 끝날 때 $A$ 는 $0$ 으로 초기화된다.

Rikka가 받는 공격의 총합이 최소가 되도록 어느 날에 질문에 답할지 정하라.

첫째 줄에 세 정수 $n$ , $K$ , $T$ 가 주어진다( $1 \leq K < n \leq 2 \times 10^5$ , $1 \leq T \leq 10^9$ ).

둘째 줄에 $n$ 개의 정수 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq T$ )이 주어진다.

정답을 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 최적의 계획은 1일차와 3일차에 질문에 답하는 것이다.