AT_past202309_h 休暇

あなたは明日からの $ N $ 日間の休暇の予定を立てようとしています。 それぞれの日には「遊ぶ」「宿題をする」のどちらかを行います。 $ N $ 日間のうち $ M $ 日以上宿題をする日がある必要があります。 $ 2 $ 日以上連続で宿題をすることはしません。 $ i $ 日目に遊ぶと、**楽しさ** を $ A_i $ 得ます。宿題をするとその日の楽しさは $ 0 $ です。 $ N $ 日間で得られる楽しさの合計の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ \ldots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 $ 1,3,5 $ 日目に遊び、 $ 2,4 $ 日目に宿題をすることで、楽しさ $ 12 $ を得ます。 ### Sample Explanation 2 $ 2,3,5 $ 日目に遊び、 $ 1,4 $ 日目に宿題をすることで、楽しさ $ 11 $ を得ます。 $ 2 $ 日以上連続して宿題をすることはできないことに注意してください。 ### Constraints - $ 1 \leq N \leq 3000 $ - $ 0 \leq M \leq \frac{N+1}{2} $ - $ 1 \leq A_i \leq 10^9 $ - 入力は全て整数である