双端队列

题目描述

你从朋友那里收到了一个 dequeue $D$ 作为生日礼物。

$D$ 是一根左右很长的筒,里面一列排着 $N$ 颗宝石。

宝石的价值从左到右依次为 $V_1, V_2, ..., V_N$。有时候也会塞着价值为负的宝石。

一开始,你一颗宝石也没有。

你可以对 $D$ 执行以下 4 种操作中任意一种,最多进行 $K$ 次:

• 操作 A:取出 $D$ 中最左端的宝石并得到它。若 $D$ 为空,则无法执行此操作。

• 操作 B:取出 $D$ 中最右端的宝石并得到它。若 $D$ 为空,则无法执行此操作。

• 操作 C:从你拥有的宝石中选 1 颗,塞到 $D$ 的最左端。若你没有宝石,则无法执行此操作。

• 操作 D:从你拥有的宝石中选 1 颗,塞到 $D$ 的最右端。若你没有宝石,则无法执行此操作。

求操作结束后你所拥有的宝石价值总和的最大值。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出操作结束后你所拥有的宝石价值总和的最大值。

样例

6 4
-10 8 2 1 2 6

14

按下面的顺序操作,可以分别得到 1 颗价值 $8$ 和 1 颗价值 $6$ 的宝石,此时价值总和 $14$ 最大。

• 执行操作 A,从 $D$ 的左端取出价值 $-10$ 的宝石。

• 执行操作 B,从 $D$ 的右端取出价值 $6$ 的宝石。

• 执行操作 A,从 $D$ 的左端取出价值 $8$ 的宝石。

• 执行操作 D,把价值 $-10$ 的宝石塞到 $D$ 的右端。

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

44

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

0

不执行任何操作是最优的。

数据范围

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