题目描述

你的朋友给了你一个双端队列 $D$ 作为生日礼物。

$D$ 是一个水平圆柱体，其中包含了一排长度为 $N$ 的珠宝。

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

一开始，你手中没有任何珠宝。

你可以对 $D$ 进行最多 $K$ 次操作，每种操作最多进行 $K$ 次（可能为零）：

• 操作 A：从 $D$ 中取出最左边的珠宝并拿在手中。当 $D$ 为空时不能进行此操作。

• 操作 B：从 $D$ 中取出最右边的珠宝并拿在手中。当 $D$ 为空时不能进行此操作。

• 操作 C：选择手中的一个珠宝，将其插入到 $D$ 的最左端。当你手中没有珠宝时不能进行此操作。

• 操作 D：选择手中的一个珠宝，将其插入到 $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$

输出

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

示例输入1

6 4
-10 8 2 1 2 6

示例输出1

14

经过以下操作序列后，你手中有价值为 $8$ 和 $6$ 的两颗珠宝，总价值为 $14$，这是最大的结果。

• 进行操作 A。你从 $D$ 的最左端取出价值为 $-10$ 的珠宝。
• 进行操作 B。你从 $D$ 的最右端取出价值为 $6$ 的珠宝。
• 进行操作 A。你从 $D$ 的最左端取出价值为 $8$ 的珠宝。
• 进行操作 D。你将价值为 $-10$ 的珠宝插入到 $D$ 的最右端。

示例输入2

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

示例输出2

44

示例输入3

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

示例输出3

0

最优解是不进行任何操作。