Problem:
 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.

Solution (Python):
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N, K = iip(False)
    V = iip(True)

    gsize = N+1

    dp1 = [[None for i in range(gsize)] for i in range(gsize)]
    dp1[0][0] = 0
    for i, value in enumerate(V, 1):
        for j in range(gsize):
            if dp1[i-1][j] is not None:
                dp1[i][j] = dp1[i-1][j] + value

            v = dp1[i-1][j-1]
            if j >= 1 and dp1[i-1][j-1] is not None:
                vv = dp1[i][j]
                if vv is not None:
                    v = max(v, vv)
                dp1[i][j] = v

    V.reverse()
    dp2 = [[None for i in range(gsize)] for i in range(gsize)]
    dp2[0][0] = 0
    for i, value in enumerate(V, 1):
        for j in range(gsize):
            if dp2[i - 1][j] is not None:
                dp2[i][j] = dp2[i - 1][j] + value

            v = dp2[i - 1][j - 1]
            if j >= 1 and dp2[i - 1][j - 1] is not None:
                vv = dp2[i][j]
                if vv is not None:
                    v = max(v, vv)
                dp2[i][j] = v

    mm = 0
    for i1 in range(gsize):
        for j1 in range(gsize):
            for i2 in range(gsize):
                for j2 in range(gsize):
                    if dp1[i1][j1] is None:
                        continue
                    if dp2[i2][j2] is None:
                        continue

                    kh = dp1[i1][j1]+dp2[i2][j2]
                    if i1 + i2 + j1 + j2 > K:
                        continue
                    if i1 + i2 > N:
                        continue

                    mm = max(kh, mm)


    
    
    
    

    return mm




def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, input().split())
X = list(map(int, input().split()))
r = -10**18
for i in range(-1, N):

    for j in range(i+1, N+1):
        A, B = X[:i+1], X[j:]
        if i+1+N-j > K:
            continue
        C = sorted(A+B)[::-1]

        for _ in range(K-(i+1+N-j)):
            if not C:
                break
            c = C.pop()
            if c > 0:
                C.append(c)
                break
        r = max(r, sum(C))
print(r)

Solution (Python):
from collections import deque
import heapq

n,k = map(int,input().split())
v = list(map(int,input().split()))

ans = 0
for i in range(1,min(n,k)+1):
    for j in range(i+1):
        s = []
        heapq.heapify(s)
        res = 0
        num = 0
        for _ in range(j):
            heapq.heappush(s,v[num])
            res += v[num]
            num += 1
        num = 1
        for _ in range(j,i):
            heapq.heappush(s,v[-num])
            res += v[-num]
            num += 1

        for j in range(k-i):
            if len(s) == 0:
                break
            if s[0] < 0:
                res -= heapq.heappop(s)
            else:
                break
        if ans < res:
            ans = res
print(ans)

Solution (Python):
from collections import deque
import heapq

n,k = map(int,input().split())
v = list(map(int,input().split()))






ans = 0
for i in range(1,min(n,k)+1):
    for j in range(i+1):
        s = []
        heapq.heapify(s)
        res = 0
        num = 0
        for _ in range(j):
            heapq.heappush(s,v[num])
            res += v[num]
            num += 1
        num = 1
        for _ in range(j,i):
            heapq.heappush(s,v[-num])
            res += v[-num]
            num += 1

        for j in range(k-i):
            if len(s) == 0:
                break
            if s[0] < 0:
                res -= heapq.heappop(s)
            else:
                break
        if ans < res:
            ans = res
    
print(ans)

Solution (Python):
import numpy as np

def main():
    N, K = [int(i) for i in input().split()]
    v = [int(i) for i in input().split()]
    res = 0
    max_ext = min(K, N)
    for ext in range(1, max_ext + 1):
        for a in range(ext+1):
            v_ext = v[:a]
            if a < ext:
                v_ext += v[-(ext-a):]
            v_ext = sorted(v_ext)
            max_ret = K - ext
            cnt_neg = 0
            for i in range(min(max_ret, ext)):
                if v_ext[i] < 0:
                    cnt_neg += 1
            res = max(res, sum(v_ext[cnt_neg:]))

    print(res)



if __name__ == '__main__':
    main()

Solution (Python):
def resolve():
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
    ans=0
    minus=0
    for i in range(k+1):
        for j in range(i+1):
            if j<=n:
              for t in range(j+1):
                w=sorted(v[:j-t] + v[n -t:])
                for l in w[:i-j]:
                    if l<0:
                       minus+=l
                ans=max(ans,(sum(w)-minus))
                minus=0
            else:
                for t in range(j + 1):
                    w = sorted(v)
                    for l in w[:i - j]:
                        if l < 0:
                            minus += l
                    ans = max(ans, (sum(w) - minus))
                    minus = 0
    print(ans)
resolve()

Solution (Python):
N,K = map(int, input().split())
V = list(map(int, input().split()))

ops = min(N,K)

ans = 0
for A in range(0,ops+1):
    l = V[:A]
    l.sort()
    for B in range(0,ops+1-A):
        ll = l[:]
        if B > 0:
            ll = l + V[-B:]
            ll.sort()
        for i in range(0,min(K-(A+B),A+B)):
            if ll[i] < 0:
                ll[i] = 0
            else:
                break
        ans = max(sum(ll),ans)

print(ans)

Solution (Python):
n, k = map(int, input().split())
V = list(map(int, input().split()))


def dfs(left, right, k):
    if left > right:
        return 0
    if k == 0:
        return 0
    if (left, right, k) in memo:
        return memo[(left, right, k)]

    l1 = V[left] + dfs(left + 1, right, k - 1)
    l2 = dfs(left + 1, right, k - 2) if k >= 2 else 0
    r1 = V[right] + dfs(left, right - 1, k - 1)
    r2 = dfs(left, right - 1, k - 2) if k >= 2 else 0
    memo[(left, right, k)] = max([l1, l2, r1, r2, 0])
    return memo[(left, right, k)]


memo = {}
print(dfs(0, n-1, k))

Solution (Python):
N,K = map(int,input().split())
V = list(map(int,input().split()))
take_chance = min(N,K)
ans = 0
for A in range(take_chance+1):
    for B in range(take_chance-A+1):
        sum1 = 0
        take = sorted(V[0:A] + V[N-B:N])
        suteru_chance = min(len(take),K-(A+B))
        sum1 = sum(take)
        for i in range(suteru_chance):
            if(take[i]<0):
                sum1 -= take[i]
        ans = max(ans,sum1)
print(ans)

Solution (Python):
N, K = map(int, input().split())
V = list(map(int,input().split()))

ans = -1 * float("INF")
for l in range(K+1):
  for r in range(K+1-l):
    if l + r > N:
      break
    d = K - l - r
    s = V[0:l] + V[N-1:N-1-r:-1]
    value = sum(s)
    s.sort()
    for i in range(d):
      if i >= len(s):
        break
      if s[i] < 0:
        value -= s[i]
      else:
        break
    ans = max(ans, value)
print(ans)

Solution (Python):
import heapq as hq

N,K=map(int,input().split())
V=list(map(int,input().split()))

ans=0
for i in range(1,min(N,K)+1): 
    for j in range(i+1):
        A=[]
        hq.heapify(A) 
        for k in range(j):
            hq.heappush(A,V[k])
        for k in range(i-j):
            hq.heappush(A,V[N-k-1])
        p=min(i,K-i) 
        while p>0:
            if A[0]<0:
                hq.heappop(A)
                p-=1
            else:
                break
        ans=max(sum(A),ans)
print(ans)

Solution (Python):
n,k=map(int,input().split())
v=list(map(int,input().split()))
ans=-10**18
for l in range(min(n,k)+1):
  for r in range(min(n,k)+1):
    if l+r>n or l+r>k:
      continue
    trg=v[:l]+v[n-r:]
    trg.sort(reverse=True)
    for i in range(k-l-r+1):
      ans=max(ans,sum(trg[:len(trg)-i]))
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    N,K = map(int, input().split())
    V_l = list(map(int, input().split()))
    V_r = list(reversed(V_l))
    res = 0
    for i in range(K+1):
        if i<=N:
            for l in range(i+1):
                n = []
                r = i - l
                a = V_l[:l] + V_r[:r]
                for j in a:
                    if j<0:
                        n.append(j)
                n.sort()
                temp = sum(a)-sum(n[:K-i])
                res = max(res, temp)

    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
a = min(n,k)
v = [0] + list(map(int,input().split()))
ans = 0
sl = 0
ml = []
for i in range(a+1):
  sl += v[i]
  if v[i] < 0:
    ml += [v[i]]
  ml.sort()
  m = ml+[]
  s = sl+0
  ans = max(ans,s-sum(m[:min(len(m),k-i)]))
  for j in range(n,max(i,n-k+i),-1):
    s += v[j]
    if v[j] < 0:
      m += [v[j]]
    m.sort()
    ans = max(ans,s-sum(m[:min(len(m),k-i-(n-j+1))]))
print(ans)

Solution (Python):

n,k=map(int,raw_input().split())
v=map(int,raw_input().split())
res=[]
for i in range(n+1):
 for j in range(min(n-i,k-i)+1):
  p=v[:i]+v[n-j:]
  p.sort()
  for x in range(k-i-j+1):
   res.append(sum(p[x:]))
print max(res)

Solution (Python):

import copy

n, k = map(int, input().split())
v = list(map(int, input().split()))
rev = copy.copy(v)
rev.reverse()

ans = -10**20
for l in range(n+1):
  for r in range(n+1-l):
    able = True
    d = k - ( l + r )
    if d < 0:
      able = False
      break
    t = v[0:l] + rev[0:r]
    m = sum(t)
    t.sort()
    d = min(d,l+r)
    for i in range(d):
      if 0 > t[i]:
        m -= t[i]
      else:
        break
    ans = max(ans,m)

print(ans)

Solution (Python):

import copy
import numpy as np

n, k = map(int, input().split())
v = list(map(int, input().split()))
rev = copy.copy(v)
rev.reverse()

lcs = [0]+np.cumsum(v)
rcs = [0]+np.cumsum(rev)


ans = -10**20
for l in range(n+1):
  for r in range(n+1-l):
    able = True
    d = k - ( l + r )
    if d < 0:
      able = False
      break
    
    t = v[0:l] + rev[0:r]
    m = sum(t)
    
    t.sort()
    
    d = min(d,l+r)
    for i in range(d):
      if 0 > t[i]:
        m -= t[i]
      else:
        break
    
    ans = max(ans,m)

print(ans)

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for i in range(N + 1):
    for j in range(N + 1):
        if i + j > N or i + j > K:
            continue
        removed = sorted(V[:i] + V[N-j:])
        sm = sum(removed)
        for k in range(K - i - j):
            if k < len(removed) and removed[k] < 0:
                sm -= removed[k]
        ans = max(ans, sm)
print(ans)

Solution (Python):
import bisect
n, k = map(int, input().split())
V = list(map(int, input().split()))
max_dequeue = min(n, k)

max_value = 0
for dequeue_num in range(max_dequeue + 1):
  for left in range(dequeue_num + 1):
    right = dequeue_num - left
    
    jewel_taken = sorted(V[:left] + V[n - right:])
    
    pos_zero = bisect.bisect(jewel_taken, 0)
    ret_num = min(k - dequeue_num, pos_zero)
    
    
    
    max_value = max(max_value, sum(jewel_taken[ret_num:]))
print(max_value)

Solution (Python):
import heapq
n, k = map(int, input().split())
v = list(map(int, input().split()))

result = []
for i in range(min(n, k)+1):
    for j in range(min(n, k)+1-i):
        x = v[:i]+v[n-j:]
        c = k - (i + j)
        x.sort()
        for t in range(min(len(x), c)):
            if x[0]<0:
                x.pop(0)
            else:
                break
        result.append(sum(x))
print(max(result))

Solution (Python):
from collections import deque
N, K = map(int, input().split())
V = list(map(int, input().split()))
R = min(N, K)
ans = 0
for A in range(R+1):
    for B in range(R+1):
        d = deque(V)
        if A + B > R:
            continue
        x = []
        for _ in range(A):
            if 0 < len(d):
                x.append(d.popleft())
        for _ in range(B):
            if 0 < len(d):
                x.append(d.pop())
        x.sort()
        drop = K - (A + B)
        for _ in range(drop):
            if 0 < len(x) and x[0] < 0:
                x.pop(0)
        ans = max(ans, sum(x))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
v_rev = v[::-1]
ans = -float("inf")

for a in range(min(n, k) + 1):
    b_list = [i for i in range(min(n, k) - a + 1)]
    for b in b_list:
        c = k - (a + b)
        left = v[:a]
        right = v_rev[:b]
        minus_list = []
        for i in left:
            if i < 0:
                minus_list.append(i)
        for j in right:
            if j < 0:
                minus_list.append(j)
        minus_list.sort()
        res = sum(left) + sum(right) - sum(minus_list[:c])
        
        
        ans = max(ans, res)
print(ans)

Solution (Python):
n, k, *V = map(int, open(0).read().split())
def calc(i, j, k):
    W = sorted(V[:i] + V[:-j-1:-1], reverse=True)
    for _ in range(k):
        if W[-1] < 0:
            W.pop()
    return sum(W)

ans = 0
r = min(n, k)+1
for i in range(r):
    for j in range(r-i):
        for k_ in range(min(i+j, k+1-i-j)):
            ans = max(ans, calc(i, j, k_))
print(ans)

Solution (Python):
from collections import deque

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
def calc(ii, jj, kk):
    W = []
    for i in range(ii):
        W.append(V[i])
    for j in range(jj):
        W.append(V[-j-1])
    W.sort(reverse=True)
    for _ in range(kk):
        if W[-1] < 0:
            W.pop()
    return sum(W)

ans = 0
for i in range(min(n, k)+1):
    for j in range(min(n, k)+1-i):
        for k_ in range(min(i+j, k+1-i-j)):
            ans = max(ans, calc(i, j, k_))
print(ans)

Solution (Python):
from collections import deque

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
def calc(ii, jj, kk):
    W = []
    for i in range(ii):
        W.append(V[i])
    for j in range(jj):
        W.append(V[-j-1])
    W.sort(reverse=True)
    for _ in range(kk):
        if W[-1] < 0:
            W.pop()
    return sum(W)

ans = 0
for i in range(min(n, k)+1):
    for j in range(min(n, k)+1-i):
        for k_ in range(min(i+j, k+1-i-j)):
            ans = max(ans, calc(i, j, k_))
print(ans)

Solution (Python):

import heapq
n, k = map(int, input().split())
v = list(map(int, input().split()))

ans = 0
for x in range(1, min(n, k)+1):
    for l in range(0, x+1):
        r = x - l
        v_ = v[:l] + v[n-r:]
        heapq.heapify(v_)
        for _ in range(k-x):
            if len(v_) == 0:
                break
            if v_[0] < 0:
                heapq.heappop(v_)
            else:
                break
        ans = max(ans, sum(v_))
        
print(ans)

Solution (Python):
from collections import deque

n, k = map(int, input().split())
v = deque(list(map(int, input().split())))
m = min(n, k)
ans = 0
for i in range(m + 1):
    for j in range(m + 1 - i):
        w = deque(v)
        a = []
        for _ in range(i):
            p = w.pop()
            a.append(p)
        for _ in range(j):
            p = w.popleft()
            a.append(p)
        a.sort()
        for l in range(min(k - i - j, len(a))):
            if a[l] < 0:
                a[l] = 0
            else:
                break
        if sum(a) > ans:
            ans = sum(a)
print(ans)

Solution (Python):
n,k = map(int,input().split())
v =  list(map(int,input().split()))

ans = 0
for i in range(1,n+1):
    vt =  v[i:][::-1] + v[:i]
    

    for j in range(0, min(n,k)+1):
        tmp = sorted(vt[:j])
        tmp_n = sum(tmp)
        for l in range(min(k-j, j)):
            if(tmp[l] < 0):
                tmp_n -= tmp[l]
        ans = max(ans, tmp_n)

print(ans)

Solution (Python):
N,K = map(int,(input().split()))
V = list(map(int,(input().split())))
left = [0]*(N+1)
right = [0]*(N+1)
ans = []

for i in range(1,N+1):
    left[i] = left[i-1] + V[i-1]

for i in range(1,N+1):
    right[i] = right[i-1] + V[N-i]


for i in range(min(N+1,K+1)):
    negal = []

    l = i
    for count in range(l):
        if l > 0 and V[count] < 0:
            negal.append(V[count])

    for j in range(min(N+1-i,K+1-i)):
        negar = []

        r = j
        for count in range(1,r+1):
            if r > 0 and V[N-count] < 0:
                negar.append(V[N-count])

        b = max(0,K-i-j)
        now = left[i] + right[j]

        nega = []
        nega.extend(negal)
        nega.extend(negar)
        nega.sort()
        s = 0
        for k in range(min(b,len(nega))):
            s += nega[k]
        
        if nega:
            ans.append(now-s)
        else:
            ans.append(now)

print(max(ans))

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, input().split())
V = list(map(int, input().split()))


@lru_cache(maxsize=None)
def solve(l, r):
    get = V[:l] + (V[-r:] if r != 0 else [])
    get.sort()
    minus = [x for x in get if x < 0]
    plus = [x for x in get if x >= 0]

    s = sum(plus) + sum(minus[K-l-r:])

    if (l + r) < N and (l + r) < K:
        get_left = solve(l + 1, r)
        get_right = solve(l, r + 1)
        s = max(s, get_left, get_right)

    return s


ans = solve(0, 0)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

def main(): 
    n,k = map(int,input().split())
    v = list(map(int,input().split()))
    
    
    ans = 0
    for l in range(n+1):
        for r in range(n-l,-1,-1):
            take = k - r - l
            if take < 0:
                continue
            tot = sum(v[:l])
            if r != 0:
                tot += sum(v[-r:])
            
            if take == 0:
                ans = max(ans,tot)
            else:
                minus = []
                for i in range(l):
                    if v[i] < 0:
                        minus.append(v[i])
                for i in range(n-1,n-r-1,-1):
                    if v[i] < 0:
                        minus.append(v[i])
                minus.sort()
                tot -= sum(minus[:take])
                ans = max(ans,tot)
    
    print(ans)
   
if __name__=='__main__':
    main()

Solution (Python):
import bisect
from collections import Counter, deque





import math

import sys



ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int,ipti().split()))
    v = list(map(int,ipti().split()))

    
    pop_max = min(k,n)
    ans = 0

    for pop in range(pop_max + 1):
        push = k - pop
        for left in range(pop + 1):
            right = pop - left
            got_jewel = v[0:left]
            if right > 0:
                got_jewel.extend(v[-right:])

            got_jewel.sort()
            negative_count = bisect.bisect_left(got_jewel, 0)
            n_push = min(push, negative_count)
            value = sum(got_jewel[n_push:])
            ans = max(ans, value)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq as pq
from collections import deque
from itertools import accumulate
N,K = map(int,input().split())
v = list(map(int,input().split()))
acc = [0]+list(accumulate(v,lambda x,y: x+y))
anss = -1
M = min(K,N)
for k in range(M+1):
    for i in range(k+1):
        ans = 0
        ls = deque(v)
        heap = []
        j = k-i
        ans += acc[i]+acc[-1]-acc[-1-j]
        for q in range(i):
            if ls:
                pq.heappush(heap,ls.popleft())
            else:
                break
        for q in range(j):
            if ls:
                pq.heappush(heap,ls.pop())
            else:
                break
        for i in range(K-k):
            if heap:
                x = pq.heappop(heap)
                if x < 0:
                    ans -= x
                else:
                    break
        anss = max(ans,anss)
print(anss)

Solution (Python):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys



"""
import copy
from collections import *
from heapq import *
N,K=map(int,input().split())
VVV=list(map(int,input().split()))
value=0

VV=deque(VVV)
Llst=[[]]
V=copy.copy(VV)
for i in range(min(K,N)):
    Llst.append(copy.copy(Llst[-1]))
    a=V.popleft()
    Llst[-1].append(a)

Rlst=[[]]
V=copy.copy(VV)
for i in range(min(K,N)):
    Rlst.append(copy.copy(Rlst[-1]))
    a=V.pop()
    Rlst[-1].append(a)


for l in range(min(K,N)+1):
    for r in range(min(K,N)+1-l):
        lst=Llst[l]+Rlst[r]
        lst.sort(reverse=True)
        for i in range(K-l-r):
            if lst:
                if lst[-1]<0:
                    lst.pop()
                else:
                    break
            else:
                break
        value=max(value,sum(lst))
print(value)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left

n, k = map(int, input().split())
v = list( map(int, input().split()))

amax = min(n,k)
ans = 0
for a in range(amax+1):
    bmax = amax - a
    for b in range(bmax+1):

        getlist = v[:a] + v[n-b:]
        getlist.sort()
        cdmax = k - a - b
        zero_index = bisect_left(getlist, 0)
        start = min(zero_index, cdmax)
        tmp = sum(getlist[start:])
        ans = max(ans, tmp)

print(ans)

Solution (Python):
import heapq

N, K = map(int,input().split())
V = list(map(int,input().split()))

num = min(N, K)

lst = []

for i in range(1,num+1):
    for j in range(i+1):
        lst.append([j,i-j,K-i])

MAX = -100000000

for A, B, p in lst:
    tmp = sum(V[:A]) + sum(V[N-B:])
    D = V[:A] + V[N-B:]
    heapq.heapify(D)
    for _ in range(p):
        if not D:
            break
        k = heapq.heappop(D)
        if k >= 0:
            break
        else:
            tmp -= k
    if tmp > MAX:
        MAX = tmp

print(MAX)

Solution (Python):
n,k = map(int,input().split())
l = list(map(int,input().split()))

def count(a,b):
    if a+b >= n:
        ans = l
    else:
        if b == 0:
            ans = l[:a]
        else:
            ans = l[:a]+l[-b:]

    check = sum(ans)
    
    if k-a-b> 0:
        ans.sort()

        for i in range(min(k-a-b,len(ans))):
            if ans[i] < 0:
                check -= ans[i]
            else:
                break
    return check
sub = 0
for i in range(min(n,k)+1):
    for j in range(min(n,k)-i+1):
        sub = max(sub,count(i,j))
print(sub)

Solution (Python):
import heapq
from collections import deque
from copy import copy
n,k = map(int,input().split())
d = deque(list(map(int,input().split())))
maxvalue = 0
for i in range(k+1):
    for j in range(k-i+1):
        jewel = []
        x = copy(d)
        for _ in range(i):
            if x:
                jewel.append(x.popleft())
        for _ in range(j):
            if x:
                jewel.append(x.pop())
        heapq.heapify(jewel)
        for _ in range(k-i-j):
            if jewel:
                a = heapq.heappop(jewel)
                if a >= 0:
                    jewel.append(a)
                    break
        maxvalue = max(maxvalue,sum(jewel))
print(maxvalue)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
V = list(map(int, input().split())) 

ans = 0
for l in range(K+1):
    left = V[:l]
    for r in range(K+1):
        if l+r > K or l+r > N:
            break
        if r != 0:
            pick = left + V[-r:]
        else:
            pick = left
        for i in range(K+1):
            if l+r+i >K:
                break
            if l+r >= i:
                pick.sort()
                ans = max(ans, sum(pick[i:]))
print(ans)

Solution (Python):

from collections import deque
from heapq import heappop, heappush
def main():
    n, k = map(int, input().split())
    vs = [int(i) for i in input().split()]
    ans = 0
    for l in range(k+1):
        for r in range(k-l+1):
            dl = k-l-r
            q = deque(vs)
            hav = []
            for _ in range(l):
                if len(q) == 0:
                    continue
                v = q.popleft()
                heappush(hav, v)
            for _ in range(r):
                if len(q) == 0:
                    continue
                u = q.pop()
                heappush(hav, u)
            for i in range(dl):
                if len(hav) == 0:
                    break
                val = heappop(hav)
                if val > 0:
                    heappush(hav, val)
            ans = max(ans, sum(hav))
    print(ans)
main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        vl = v[:l]
        for r in range(min(k,n)+1-l):
            vr = v[n-r:]
            s = max(0,k-l-r)
            nv = vl+vr
            nv.sort(reverse = True)
            while s > 0 and nv and nv[-1] < 0:
                nv.pop()
                s -= 1
            su = sum(nv)
            if ans < su:
                ans = su
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  cnt=min(n,k)
  ans=0
  for i in range(cnt+1):
    for j in range(cnt-i+1):
      q=[]
      for _i in range(i):
        heapq.heappush(q,l[_i])

      for _j in range(j):
        heapq.heappush(q,l[-(_j+1)])

      ln=len(q)
      for _ in range(min(k-i-j,ln)):
        x=heapq.heappop(q)
        if x>0:
          q.append(x)
          break
      
      ans=max(ans,sum(q))

  return ans


print(main())