AT_codequeen2024_final_c Attraction on Rainy Day

高橋君は 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 $ とし、アトラクションから降りた時刻に新たにアトラクションに乗ることができるものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ T $ $ P_0 $ $ P_1 $ $ \ldots $ $ P_{N-1} $

答えを出力せよ。

### Sample Explanation 1 次のようにアトラクションに $ 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 $ 濡れる。 ### Constraints - $ 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} $ - 入力は全て整数