No.324 落ちてた閉路グラフ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 50
作問者 : tubo28tubo28

5 ProblemId : 879 / 出題時の順位表

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 \leq n \leq 3000$
  • $0 \leq m \leq n$
  • $-300 \leq w_{i} \leq 300$

出力

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

サンプル

サンプル1
入力
6 3
1 2 3 4 5 6
出力
11
サンプル2
入力
6 3
1 -2 -3 4 -5 6
出力
7
サンプル3
入力
6 3
-1 -2 -3 -4 -5 -6
出力
0
サンプル4
入力
6 4
-1 -2 -3 -4 -5 -6
出力
-3
提出ページヘ