题目描述

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

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

这些宝石的价值从左到右分别是 $V_1,V_2...V_N$。宝石的价值可以是负数。

一开始，你手上没有任何宝石。 你可以在 $D$ 上执行最多 $K$ 次操作，每种操作最多执行 $K$ 次(可以不执行):

A 操作:从 $D$ 的左端取出最左侧的宝石并带在手上。当 $D$ 为空时，无法执行此操作。

B 操作:从 $D$ 的右端取出最右侧的宝石并带在手上。当 $D$ 为空时，无法执行此操作。

C操作:选择手上的一个宝石，并将它插入到 $D$ 的左端。当手上没有宝石时，无法执行此操作

D 操作:选择手上的一个宝石，并将它插入到 $D$ 的右端。当手上没有宝石时，无法执行此操作。

找到在操作之后，你手上的宝石的价值之和的最大可能值。

输入

第一行两个整数$N,K$

第二行$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

样例解释

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

提示

$1 \leq N \leq 50$

$1 \leq K \leq 100$

$-10^7 \leq V_i \leq 10^7$