配点 : $400$ 点

問題文

あなたは誕生日プレゼントとして友人から dequeue $D$ を貰いました。

$D$ は左右に長い筒であり、$N$ 個の宝石が一列に詰められています。

宝石の価値は左から順に $V_1, V_2, ..., V_N$ です。負の価値の宝石が詰められている場合もあります。

はじめ、あなたは $1$ つも宝石を持っていません。

あなたは、$D$ に対して以下の $4$ 種類の操作から $1$ つを選んで実行することを $K$ 回まで行うことができます。

• 操作 A: $D$ に詰められた宝石のうち、左端の宝石を取り出して手に入れる。$D$ が空の場合、この操作を行えない。
• 操作 B: $D$ に詰められた宝石のうち、右端の宝石を取り出して手に入れる。$D$ が空の場合、この操作を行えない。
• 操作 C: 持っている宝石を $1$ つ選んで $D$ の左端に詰める。宝石を持っていない場合、この操作を行えない。
• 操作 D: 持っている宝石を $1$ つ選んで $D$ の右端に詰める。宝石を持っていない場合、この操作を行えない。

操作終了後に持っている宝石の価値の合計の最大値を求めてください。

制約

• 入力は全て整数である。
• $1 \leq N \leq 50$
• $1 \leq K \leq 100$
• $-10^7 \leq V_i \leq 10^7$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$V_1$ $V_2$ $...$ $V_N$

出力

操作終了後に持っている宝石の価値の合計の最大値を出力せよ。

6 4
-10 8 2 1 2 6

14

以下の順に操作を行うことで、価値 $8, 6$ の宝石をそれぞれ $1$ 個ずつ手に入れることができ、このときの合計価値 $14$ が最大です。

• 操作 A を行い、$D$ の左端から価値 $-10$ の宝石を取り出します。
• 操作 B を行い、$D$ の右端から価値 $6$ の宝石を取り出します。
• 操作 A を行い、$D$ の左端から価値 $8$ の宝石を取り出します。
• 操作 D を行い、$D$ の右端に価値 $-10$ の宝石を詰めます。

6 4
-6 -100 50 -2 -5 -3

44

6 3
-6 -100 50 -2 -5 -3

0

操作を行わないのが最適です。