Note

この問題は Advent Calendar Contest Advent Calendar 2015 の 17 日目の問題として作られました．

問題文

ある日 yuki さんが道を歩いていると，すごそうな閉路グラフが落ちているのを見つけました．
グラフは $n$ 個の辺と頂点からなり，辺には時計回りに $1$ から $n$ までの番号がつけられています．
辺 $i$ の価値は $w_i$ です．

興味を持った yuki さんは，このグラフをネコババすることにしました．
yuki さんのバッグにはちょうど $m$ 個の頂点が入るので，$m$ 頂点の誘導部分グラフを持ち帰ることにしました．
つまり，ある辺の両端の頂点を持ち帰ることにした場合は，その辺を必ず持ち帰らなければいけません．
部分グラフの価値を含まれる辺の価値の合計とします．
持ち帰ることができるグラフの価値の最大値を求めてください．

入力

$n$ $m$
$w_1{w}_2{w}_3\cdots w_n$

以下の制約を満たします．

• 全て整数
• $3\le n\le 3000$
• $0\le m\le n$
• $-300\le w_i\le 300$

出力

答えを $1$ 行に出力し，最後に改行を出力してください．

サンプル

6 3
1 2 3 4 5 6

11

6 3
1 -2 -3 4 -5 6

7

6 3
-1 -2 -3 -4 -5 -6

0

6 4
-1 -2 -3 -4 -5 -6

-3