Rikka with RCPC

Rikka is going to hold a worldwide competition, RCPC (Rikka's collegiate programming contest).

Preparing for the contest takes Rikka $n$ days. Meanwhile, the official QQ group of RCPC receives many questions from contestants, coaches, and even melon eating people. Rikka decides to ignore the QQ group on some of the $n$ days.

However, always ignoring questions may make contestants angry. Before the start of Day $1$, the angry value $A$ of contestants is $0$. At the beginning of the $i$-th day, the angry value increases by $a_i$. Then:

• If $A$ is strictly larger than a threshold $T$, contestants will be extremely angry, and Rikka receives $2A$ points of attack. At the end of this day, $A$ is cleared to $0$.
• If $A$ is no larger than $T$ and Rikka chooses to ignore questions, nothing happens on this day.
• If $A$ is no larger than $T$ and Rikka decides to answer questions, and Rikka ignored all questions on the previous $K$ days, i.e. from Day $i-K$ to Day $i-1$, contestants will feel the hardness of Rikka. Rikka receives no attack, and at the end of this day, $A$ is cleared to $0$.
• Otherwise, even though Rikka chooses to answer questions, contestants still blame Rikka for answering so slowly, and Rikka receives $A$ points of attack. At the end of this day, $A$ is cleared to $0$.

Your task is to decide which days to answer questions so that the total attack Rikka receives is minimized.

The first line contains three integers $n$, $K$, and $T$ ($1 \leq K < n \leq 2 \times 10^5$, $1 \leq T \leq 10^9$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq T$).

Output a single integer, the answer.

For the first sample, one optimal plan is to answer questions on Day $1$ and Day $3$:

• On Day $1$, the angry value is $3$, so Rikka receives $3$ points of attack.
• On Day $2$, the angry value is $1$, so nothing happens.
• On Day $3$, the angry value is $5$. Since Rikka did not answer on Day $2$, contestants feel the hardness of Rikka, so nothing happens.
• On Day $4$, the angry value is $2$, so nothing happens.