题目描述

Your friend gave you a dequeue $D$ as a birthday present.

$D$ is a horizontal cylinder that contains a row of $N$ jewels.

The values of the jewels are $V_1, V_2, ..., V_N$ from left to right. There may be jewels with negative values.

In the beginning, you have no jewel in your hands.

You can perform at most $K$ operations on $D$, chosen from the following, at most $K$ times (possibly zero):

• Operation A: Take out the leftmost jewel contained in $D$ and have it in your hand. You cannot do this operation when $D$ is empty.

• Operation B: Take out the rightmost jewel contained in $D$ and have it in your hand. You cannot do this operation when $D$ is empty.

• Operation C: Choose a jewel in your hands and insert it to the left end of $D$. You cannot do this operation when you have no jewel in your hand.

• Operation D: Choose a jewel in your hands and insert it to the right end of $D$. You cannot do this operation when you have no jewel in your hand.

Find the maximum possible sum of the values of jewels in your hands after the operations.

你的朋友送给你一个 dequeue $D$ 作为生日礼物。

$D$ 是一个水平圆柱体，里面有一排 $N$ 颗宝石。

这些珠宝的_值从左到右依次为 $V_1, V_2, ..., V_N$ 。其中可能有数值为负的珠宝。

开始时，你手中没有珠宝。

你最多可以对 $D$ 进行 $K$ 次运算，这些运算从下面的运算中选出，最多可以进行 $K$ 次运算（可能为零）：

• 操作 A：取出 $D$ 中最左边的一颗宝石并将其置于手中。当 $D$ 为空时，无法进行此操作。

• 操作 B：取出 $D$ 中最右边的宝石并将其拿在手中。当 $D$ 为空时，无法进行此操作。

• 操作 C：选择手中的一颗宝石，将其插入 $D$ 的左端。如果手中没有宝石，则无法进行此操作。

• 操作 D：选择手中的一颗宝石，并将其插入 $D$ 的右端。如果您的手中没有宝石，则无法进行此操作。

求操作后手中宝石的最大可能和。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印操作后您手中珠宝价值的最大可能总和。

样例 #1

样例输入 #1

6 4
-10 8 2 1 2 6

样例输出 #1

14

样例 #2

样例输入 #2

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

样例输出 #2

44

样例 #3

样例输入 #3

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

样例输出 #3

0

说明

数据规模与约定

• 所有输入值均为整数。
• $1 \leq N \leq 50$
• $1 \leq K \leq 100$
• $-10^7 \leq V_i \leq 10^7$

样例 $1$ 解释

经过下面一连串的运算，你手中有两颗价值为 $8$ 和 $6$ 的宝石，总价值为 $14$ ，这是最大结果。

• 执行操作 A，从 $D$ 的左端取出价值为 $-10$ 的珠宝。
• 执行操作 B，从 $D$ 的右端取出价值为 $6$ 的宝石。
• 执行操作 A。从 $D$ 的左端取出价值为 $8$ 的宝石。
• 执行操作 D. 将数值为 $-10$ 的宝石放入 $D$ 的右端。

样例 $3$ 解释

最好不进行任何操作。