問題
佐藤君は新卒で初任給をもらいました。そこで佐藤君は長年の夢であった「ここからここまで全部ください」をするべく、駄菓子屋さんに向かいました。ですが、そのお店では購入にルールがありました。佐藤君はこんなことは滅多に無いためできるだけ多くの金額を消費したいと考えました。購入のルールは以下の通りです。
- 一度に買えるのは隣合う商品のみ
- 買うとしても最大$K$個まで
入力
入力は以下の形式で標準入力から与えられる。
$N$ $K$ $A_1$ $A_2$ $A_3$ ... $A_N$
1行目に整数$N,K$が与えられる。 2行目に整数$A_i(1 \leq i \leq N)$が与えられる。
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N \leq 10^4$
- $1 \leq K \leq 10^2$
- $1 \leq A_i \leq 10^2$ $(1 \leq i \leq N)$
- $K \leq N$
入出力例
入力例1
4 2 14 3 2 11
出力例1
17
入力例2
5 5 2 3 5 7 4
出力例2
16