AT_abc218_h [ABC218H] Red and Blue Lamps

[problemUrl]: https://atcoder.jp/contests/abc218/tasks/abc218_h $ 1 $ から $ N $ の番号がついた $ N $ 個のランプが一列に並べられています。あなたはこのうち $ R $ 個を赤く、$ N-R $ 個を青く光らせようとしています。 各 $ i=1,\ldots,N-1 $ について、ランプ $ i $ とランプ $ i+1 $ が異なる色で光っているとき、あなたは $ A_i $ の報酬を得ます。 ランプの色を適切に定めたときに得られる報酬の合計の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ R $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_{N-1} $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ R\ \leq\ N-1 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - 入力に含まれる値は全て整数である ### Sample Explanation 1 ランプ $ 3,5 $ を赤く、ランプ $ 1,2,4,6 $ を青くすることで、$ A_2+A_3+A_4+A_5=11 $ の報酬を得ます。 これ以上の報酬を得ることはできないため、答えは $ 11 $ です。 ### Sample Explanation 2 ランプ $ 1,2,3,4,5,7 $ を赤く、ランプ $ 6 $ を青くすることで、$ A_5+A_6=10 $ の報酬を得ます。