問題文

高橋君は AtCoder Land にある屋外アトラクションに K 回乗ろうとしています。このアトラクションの一回の所要時間は T です。

現在の時刻は 0 です。時刻 0 から N までの降水量が与えられます。時刻 i から時刻 i+1 までの降水量は P_i です (0\leq i\lt N)。アトラクションには時刻 0,1,…,N−T に乗ることができます。時刻 t にアトラクションに乗ると時刻 t+T にアトラクションから降りることができ、アトラクションに乗っている間に P_t+P_{t+1}+\dots+P_{t+T-1} だけ濡れます。

高橋君はアトラクションに乗っている間にできるだけ雨に濡れないようにしたいです。時刻 N までに K 回アトラクションに乗るとき、高橋君が濡れる量の総和の最小値を求めてください。ただし、乗り換えにかかる時間や待ち時間は 0 とし、アトラクションから降りた時刻に新たにアトラクションに乗ることができるものとします。

制約

• 1\leq N\leq 2\times 10^5
• 1\leq K\leq \min(N,100)
• 1\leq T\leq N/K
• 0\leq P_i\leq 10^{9}
• 入力は全て整数

入力例 1

8 3 2
3 5 10 4 1 7 3 9

出力例 1

23

次のようにアトラクションに 3 回乗ることで濡れる量を合計で 23 にすることができ、これが最小です。

• アトラクションに時刻 0 に乗り、時刻 2 に降りる。この間に P_0+P_1=3+5=8 濡れる。
• アトラクションに時刻 3 に乗り、時刻 5 に降りる。この間に P_3+P_4=4+1=5 濡れる。
• アトラクションに時刻 5 に乗り、時刻 7 に降りる。この間に P_5+P_6=7+3=10 濡れる。

入力例 2

5 1 3
1000 1 10000 100 10

出力例 2

10101

入力例 3

15 5 2
401054171 63773035 986525245 157986893 799814573 139201145 649233932 351289844 409065258 406122133 957285954 529460482 21179081 795984182 727882733

出力例 3

3522058414