D - 队列

得分：$400$ 分

问题描述

你的朋友送给你一个双端队列 $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$

输出

输出手上的宝石的价值之和的最大可能值。

6 4
-10 8 2 1 2 6

14

经过以下一系列的操作之后，你手上有两颗宝石，它们的价值分别是 $8$ 和 $6$，总价值为 $14$，这是最大的结果。

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

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

44

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

0

对于这个样例，最佳方案是不进行任何操作。