Home

Problem Statement

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.

Constraints

• All values in input are integers.
• $1 \leq N \leq 50$
• $1 \leq K \leq 100$
• $-10^7 \leq V_i \leq 10^7$

Sample Input 1

6 4
-10 8 2 1 2 6

Sample Output 1

14

After the following sequence of operations, you have two jewels of values $8$ and $6$ in your hands for a total of $14$, which is the maximum result.

• Do operation A. You take out the jewel of value $-10$ from the left end of $D$.
• Do operation B. You take out the jewel of value $6$ from the right end of $D$.
• Do operation A. You take out the jewel of value $8$ from the left end of $D$.
• Do operation D. You insert the jewel of value $-10$ to the right end of $D$.

Sample Input 2

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

Sample Output 2

44

Sample Input 3

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

Sample Output 3

0

It is optimal to do no operation.