Hop Hop Hamstring

問題文

正整数 $N , L , K$ と、長さ $N$ の正整数列 $A = (A_1 , A_2 ,..., A_N)$ が与えられます。

yuki 君は $10^{100}$ 円を持っており、無限に続く階段を登ろうとしています。

はじめ、yuki 君は $0$ 段目にいます。
yuki 君は、次の $2$ 種類の行動のうち一方を選んで行うことを繰り返します。

• 階段を $1$ 段登る。
• 階段を $L$ 段登る。

行動の結果、yuki 君が $t$ 段目に止まったとき、$A_t$ 円を支払わなければなりません。

また、階段を $L$ 段登る行動を $3$ 回連続で行った場合、yuki 君は肉離れを起こします。
このとき、治療費として追加で $K$ 円を支払い、それ以降は階段を $L$ 段登る行動を選ぶことができなくなります。

yuki 君がちょうど $N$ 段目に止まるような移動方法のうち、支払う金額の合計の最小値を求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq L \leq N$
• $0 \leq K \leq 10^9$
• $1 \leq A_i \leq 10^9$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

出力

yuki 君が支払う金額の最小値を出力せよ。

入力例１

5 2 100
10 1 10 1 10

出力例１

12

$0$ 段目 $\to$ $2$ 段目 $\to$ $4$ 段目 $\to$ $5$ 段目 と移動すると、支払う金額は $A_2 + A_4 + A_5 = 1 + 1 + 10 = 12$ 円です。

$11$ 円以下で移動する方法は存在しないため、 $12$ を出力してください。

入力例２

5 5 100
2 4 6 8 10

出力例２

10

$L=N$ なので、$0$ 段目から $5$ 段目へ一度で移動できます。 このとき支払う金額は $A_5=10$ 円です。

入力例３

8 2 10
100 1 100 1 100 1 1 1

出力例３

15

$0$ 段目 $\to 2$ 段目 $\to 4$ 段目 $\to 6$ 段目 $\to 7$ 段目 $\to 8$ 段目 と移動することを考えます。

最初の $3$ 回の行動では、階段を $L=2$ 段ずつ登っています。 そのため、$6$ 段目に止まった時点で肉離れを起こし、治療費として $K=10$ 円を追加で支払います。

その後は $L$ 段登る行動を選べなくなりますが、$1$ 段ずつ登ることで $8$ 段目に到達できます。

このとき支払う金額は $15$ 円で、これが最小です。

入力例４

5 2 10
1000000000 1000000000 1000000000 1000000000 1000000000

出力例４

3000000000

答えが $32$ bit 整数型に収まらない場合があることに注意してください。