101283: [AtCoder]ABC128 D - equeue
Description
Score : $400$ points
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$
Input
Input is given from Standard Input in the following format:
$N$ $K$ $V_1$ $V_2$ $...$ $V_N$
Output
Print the maximum possible sum of the values of jewels in your hands after the operations.
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.