题目描述

あなたは誕生日プレゼントとして友人から 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$ の右端に詰める。宝石を持っていない場合、この操作を行えない。

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

输入格式

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

$N$ $K$ $V_1$ $V_2$ $...$ $V_N$

输出格式

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

题目大意

题目描述

有一个双端队列，初始时队列中共有 $n$ 个元素，元素从头到尾的权值为 $v_{1},v_{2},\cdots,v_{n}$

你可以进行不超过 $k$ 次操作（也可以一次都不操作），每次操作可以选择队头或队尾的一个元素，将它归为己有，或将自己手上的一个元素塞到队头或队尾

问最终你手上所有元素的权值之和的最大值是多少

输入格式

第一行两个整数 $n,k$

接下来一行 $n$ 个整数表示 $v_{i}$

输出格式

一行一个整数，表示答案

数据范围与提示

$ 1 \le n \le 50,1 \le k \le 100, -10^7 \le v_{i} \le 10^7 $

6 4
-10 8 2 1 2 6

14

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

44

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

0

提示

制約

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

Sample Explanation 1

以下の順に操作を行うことで、価値 $8,\ 6$ の宝石をそれぞれ $1$ 個ずつ手に入れることができ、このときの合計価値 $14$ が最大です。 - 操作 A を行い、$D$ の左端から価値 $-10$ の宝石を取り出します。 - 操作 B を行い、$D$ の右端から価値 $6$ の宝石を取り出します。 - 操作 A を行い、$D$ の左端から価値 $8$ の宝石を取り出します。 - 操作 D を行い、$D$ の右端に価値 $-10$ の宝石を詰めます。

Sample Explanation 3

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