{"raw_statement":[{"iden":"problem statement","content":"Your friend gave you a dequeue $D$ as a birthday present.\n$D$ is a horizontal cylinder that contains a row of $N$ jewels.\nThe _values_ of the jewels are $V_1, V_2, ..., V_N$ from left to right. There may be jewels with negative values.\nIn the beginning, you have no jewel in your hands.\nYou can perform at most $K$ operations on $D$, chosen from the following, at most $K$ times (possibly zero):\n\n*   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.\n    \n*   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.\n    \n*   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.\n    \n*   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.\n    \n\nFind the maximum possible sum of the values of jewels in your hands after the operations."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N \\leq 50$\n*   $1 \\leq K \\leq 100$\n*   $-10^7 \\leq V_i \\leq 10^7$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$V_1$ $V_2$ $...$ $V_N$"},{"iden":"sample input 1","content":"6 4\n-10 8 2 1 2 6"},{"iden":"sample output 1","content":"14\n\nAfter 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.\n\n*   Do operation A. You take out the jewel of value $-10$ from the left end of $D$.\n*   Do operation B. You take out the jewel of value $6$ from the right end of $D$.\n*   Do operation A. You take out the jewel of value $8$ from the left end of $D$.\n*   Do operation D. You insert the jewel of value $-10$ to the right end of $D$."},{"iden":"sample input 2","content":"6 4\n-6 -100 50 -2 -5 -3"},{"iden":"sample output 2","content":"44"},{"iden":"sample input 3","content":"6 3\n-6 -100 50 -2 -5 -3"},{"iden":"sample output 3","content":"0\n\nIt is optimal to do no operation."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}