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):
def resolve():
  N, K = list(map(int, input().split()))
  V = list(map(int, input().split()))
  r = 0
  for i in range(min(N,K)+1):
    for j in range(min(N-i,K-i)+1):
      a = V[:i]+V[N-j:]
      b = [x for x in a if x<0]
      b.sort()
      rij = sum(a)-sum(b[:K-i-j])
      r = max(r, rij)
  print(r)
resolve()

Solution (Python):


import sys
input = sys.stdin.readline


N, K = map(int, input().split())
D = [int(x) for x in input().split()]


ans = 0
for l in range(N + 1):
    if l > K:
        break

    for r in range(N - l + 1):
        if l + r > K:
            break

        value_list = D[0 : l] + D[N - r : N]
        value_list.sort()
        
        for i in range(K - (l + r) + 1):
            ans = max(ans, sum(value_list[i:]))
        
print(ans)

Solution (Python):


import sys
input = sys.stdin.readline


N, K = map(int, input().split())
D = [int(x) for x in input().split()]


ans = 0
for l in range(N + 1):
    if l > K:
        break

    for r in range(N - l + 1):
        if l + r > K:
            break

        l_list = sorted(D[0 : l])
        r_list = sorted(D[N - r : N])

        for discard_l in range(K - (l + r) + 1):
            for discard_r in range(K - (l + r + discard_l) + 1):
                value = sum(l_list[discard_l:])
                value += sum(r_list[discard_r:])

                ans = max(ans, value)
        
print(ans)

Solution (Python):
N,K=map(int,input().split())
V=list(map(int,input().split()))
ans=0
for l in range(K+1):
  for r in range(K-l+1):
    a=[]
    if l+r>N:
      break
    a=V[:l]
    a.extend(V[N-r:])
    b=sum(a)
    a.sort()
    for i in range(min(K-l-r,l+r)):
      if a[i]>=0:
        break
      else:
        b-=a[i]
    ans=max(ans,b)
print(ans)

Solution (Python):
N, K = map(int, input().split())
Vlist = list(map(int, input().split()))
ret = 0
for l in range(min(N,K)+1):
    for r in range(min(N,K)-l+1):
        tem = Vlist[:l]+Vlist[N-r:]
        tem = sorted(tem)
        tem[:K-l-r] = [max(0, i) for i in tem[:K-l-r]]
        score = sum(tem)
        if ret < score:
            ret = score
print(ret)

Solution (Python):
n,k,*v=map(int,open(0).read().split())
motimono=[]
ans=[]
v*=2
for j in range(1,min(n,k)+1):
    for i in range(n-j,n+1):
        motimono=v[i:i+j]
        ans.append(sum(motimono))
        motimono.sort(reverse=1)
        for i in range(min(k-j,j)):
            del motimono[-1]
            ans.append(sum(motimono))
print(max(ans))

Solution (Python):
n,k,*v=map(int,open(0).read().split())
motimono=[]
ans=[]
v*=2
for j in range(1,min(n,k)+1):
    for i in range(n-j,n+1):
        motimono=v[i:i+j]
        ans.append(sum(motimono))
        motimono.sort()
        for i in range(min(k-j,j)):
            del motimono[0]
            ans.append(sum(motimono))
print(max(ans))

Solution (Python):
n,k,*v=map(int,open(0).read().split())
motimono=[]
ans=[]
v*=2
for j in range(1,min(n,k)+1):
    for i in range(n-j,n+1):
        motimono=v[i:i+j]
        ans.append(sum(motimono))
        motimono.sort()
        for i in range(k-j):
            if len(motimono)>0:
                del motimono[0]
            ans.append(sum(motimono))
print(max(ans))

Solution (Python):
N,K=map(int,input().split())
V=list(map(int,input().split()))+[-10**8]
ans=0
for i in range(1,K+1):
    for j in range(1,min(i+1,N+1)):
        W=sorted(V[:j]+V[-min(i,N)-1+j:],reverse=True)[:-1]
        for k in range(0,K-i):
            if W[-1]<0:
                W.pop()
                if W==[]:
                    break
            else:
                break
        if ans<sum(W):
            ans=sum(W)
print(ans)

Solution (Python):
from heapq import*
n,k=map(int,input().split())
*v,=map(int,input().split())
motimono=[]
ans=[]
v*=2
for j in range(1,min(n,k)+1):
    for i in range(n-j,n+1):
        motimono=v[i:i+j]
        ans.append(sum(motimono))
        heapify(motimono)
        for i in range(k-j):
            if len(motimono)>0:
                heappop(motimono)
            ans.append(sum(motimono))
print(max(ans))

Solution (Python):

"""
Created on Wed May 29 22:59:58 2019

@author: Yamazaki Kenichi
"""

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

ans = 0
for pickup_n in range(min(K, N)+1):
    for start in range(pickup_n + 1):
        tmp = [0]
        for i in range(pickup_n):
            tmp.append(V[i - start])
        tmp.sort()
        for i in range(K - pickup_n):
            if tmp[i] < 0:
                tmp[i] = 0
            else:
                break
        ans = max(ans,sum(tmp))
print(ans)

Solution (Python):
n,k = map(int,input().split())
v = [int(i) for i in input().split()]
jewel = []
ans = 0
for i in range(min(k+1,n+1)):
  for j in range(min(k-i+1,n-i+1)):
    jewel = v[:i] + v[:-(j+1):-1]
    jewel.sort()
    temp = sum(jewel)
    leng = len(jewel)
    for m in range(k-i-j):
      if leng > m and jewel[m] < 0:
        temp += -jewel[m]
    ans = max(ans,temp)
print(ans)

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

V_lst = list(map(int, input().split()))

NK_min = min(N, K)

Max = 0
for r in range(NK_min + 1):
    for l in range(NK_min - r + 1):
        rev = K - r - l
        having = None
        if r == 0:
            having = V_lst[:l]
        else:
            having = V_lst[:l] + V_lst[-r:]
        having.sort()
        for _ in range(rev):
            if len(having) == 0:
                break
            if having[0] < 0:
                having.pop(0)
            else:
                break

        if Max < sum(having):
            Max = sum(having)


print(Max)

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

v=[int(i) for i in input().split()]
d=[]
ans=[]

for i in range(min(N,K)+1):
    for j in range(i+1):
                
        for k in range(j):
            d.append(v[k])

        for l in range(i-j):
            d.append(v[len(v)-(l+1)])
        

        for m in range(K-i):
            if len(d)>=1:
                d.sort(reverse=True)
                if d[len(d)-1]<0:
                    d.pop()

        ans.append(sum(d))
        d=[]

print(max(ans))

Solution (Python):

"""
D - equeue
https://atcoder.jp/contests/abc128/tasks/abc128_d

"""
import sys


def dig_lr(n, q, lr='L'):
    
    res = [0]
    for di in range(1, min(n, len(q))+1): 
        bu = n - di             
        dig = list(q[:di]) if lr == 'L' else list(q[-di:])
        dig.sort()
        while bu and dig and dig[0] < 0: 
            dig.pop(0)
            bu -= 1
        res.append(sum(dig))
    return max(res)


def solve(N, K, V):
    ans = [0]
    limit = sum([v for v in V if v > 0]) 
    
    
    for left in range(K+1):
        right = K - left
        l_dig = dig_lr(left, V, 'L')
        r_dig = dig_lr(right, V, 'R')
        ans.append(min(limit, l_dig+r_dig))
    return max(ans)


def main(args):
    N, K = map(int, input().split())
    V = [int(v) for v in input().split()]
    ans = solve(N, K, V)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
N,K = map(int,input().split())
V_list = list(map(int,input().split()))
min_ = min(N,K)
total = [0]

for a in range(min_+1):
  for b in range(min_-a+1):
    score_get = V_list[:a]+V_list[N-b:]
    score_get.sort()
    score = sum(score_get)
    for i in range(min(K-(a+b),len(score_get))):
      if score_get[i]<0:
        score -= score_get[i]
      else:
        break
    total.append(score)
print(max(total))

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

for i in range(min(n, k) + 1):
    
    for j in range(min(n, k) - i + 1):
        
        par_seq = sorted(v[:i] + v[-j:] if j != 0 else v[:i])
        par_seq_sum = sum(par_seq)
        if par_seq_sum > ans:
            ans = par_seq_sum
        ope = k - (i + j)
        
        for _ in range(min(ope, len(par_seq))):
            rm = par_seq.pop(0)
            if rm < 0 and sum(par_seq) > ans:
                ans = sum(par_seq)

print(ans)

Solution (Python):
n,k=map(int,input().split())
d=list(map(int,input().split()))
d=d*2
ans=0
for i in range(1,min(k+1,n+1)):
  
  for j in range(i+1):
    have=[d[n+c-j] for c in range(i)] 
    have.sort()
    if i!=k:
      for h in range(k-i):
        if have==[] or have[0]>=0:
          break
        del have[0]
      
    if sum(have)>ans:
      ans=sum(have)
print(ans)

Solution (Python):
N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = 0
R = min(N,K)
for A in range(R+1):
    for B in range(R-A+1):
        s = V[:A]+V[N-B:]
        
        s.sort()
        S = sum(s)
        for k in range(min(K-A-B,len(s))):
            if s[k] < 0:
                S -= s[k]
        ans = max(ans,S)
print(ans)

Solution (Python):
N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = 0
R = min(N,K)
for A in range(R+1):
    for B in range(R-A+1):
        s = V[:A]+V[N-B:]
        
        s.sort()
        S = sum(s)
        for k in range(min(K-A-B,len(s))):
            
            if s[k] < 0:
                S -= s[k]
        ans = max(ans,S)
print(ans)

Solution (Python):
n, k = map(int, input().split())
v = [int(i) for i in input().split()]
res = []
for l in range(min(k+1, n+1)):
    tmp1 = v[:l]
    res.append(sum(tmp1))
    for r in range(min(k, n) - l):
        if r == 0:
            tmp2 = tmp1
        else:
            tmp2 = tmp1 + v[-r:]
        res.append(sum(tmp2))
        for a in range(min(len(tmp2), k-l-r)):
            tmp2.sort()
            tmp3 = tmp2[a+1:]
            res.append(sum(tmp3))
print(max(res))

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

ans = 0
for a in range(K+1):
    for b in range(a+1):
        if a + b > K:
            break
        for c in range(K+1):
            if a + b + c > K:
                break
            if a + c > N:
                break
            for d in range(c+1):
                if a + b + c + d > K:
                    break
                va = V[:a]
                vc = V[::-1][:c]
                va.sort(reverse = True)
                vc.sort(reverse = True)
                ans = max(ans, sum(va[:a-b]) + sum(vc[:c-d]))
print(ans)

Solution (Python):
def solve2():
    N, K = [int(_) for _ in raw_input().split()]
    V = [int(_) for _ in raw_input().split()]
    MAX_GET = min(N, K)
    ans = 0
    for i in range(MAX_GET + 1):
        for j in range(MAX_GET + 1 - i):
            get = V[:i] + V[(N - j):]
            if len(get) == 0:
                continue
            get.sort(reverse = True)
            for k in range(K - i - j):
                if len(get) > 0 and get[-1] < 0:
                    get.pop()
                else:
                    break
            ans = max(ans, sum(get))
    print ans

if __name__ == '__main__':
    solve2()

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

from bisect import bisect_left

ans = 0
for i in range(1 + min(n, k)):
    for j in range(1 + min(n, k) - i):
        if i == j == 0:
            ans = max(ans, 0)
        else:
            remk = k - i - j
            _v = v[:i] + v[n-j:]
            _v.sort()
            max_i = min(remk, bisect_left(_v, 0))
            ans = max(ans, sum(_v[max_i:]))

print(ans)

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

def solve(L, R, D):
  
  LL = v[:L] if L > 0 else []
  RR = v[-R:] if R > 0 else []
  targetList = LL + RR
  
  targetList.sort()
  ret = 0
  newList = targetList[::]
  for i in range(min(len(targetList), D)):
    if targetList[i] < 0:
      del newList[0]
  ret = sum(newList)
  
  return ret

result = 0
for i in range(min(k+1, n+1)):
  for j in range(min(k+1, n+1)-i):
    t = solve(i, j, k-i-j)
    if t > result:
      result = t

print(result)

Solution (Python):













from itertools import combinations, permutations 

from collections import deque, Counter 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace 
from copy import deepcopy, copy 
import heapq
import copy
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)
def gcds(a):
    if len(a)==1:
        return a[0]
    else:
        element = gcd(a[0], a[1])
        if len(a)==2:return(element)
        else:
            for i in range(2,n):
                element=gcd(element,a[i])
            return(element)

is_test = False
def debug_print(a,comments="",is_test=is_test):
    
    
    
    if not is_test:
        pass
    elif not comments and a is None:
        print("")
    elif not comments:
        print(a)
    else:
        print(comments,":",a)


if is_test:
    n,k = [6, 8]
    vn = [-6, -100, 50, -2, -5, -3]
    
else:        
    n,k = map(int,input().split())
    vn = [int(i) for i in input().split()]

hp = []
ans = 0
for i in range(min(k,n)+1):
    if i == 0:
        pass
    else:
        heapq.heappush(hp,vn[i-1])
    hpj = copy.deepcopy(hp)
    for j in range(min(k,n)-i+1):
        if j == 0:
            pass
        else:
            heapq.heappush(hpj,vn[n-j])
        hpjj = copy.deepcopy(hpj)
        debug_print(hpjj)
        counter = 0
        if i==0 and j==0:
            pass
        else:            
            while hpjj[0] < 0 and counter < k-i-j:
                counter += 1
                heapq.heappop(hpjj)
                if len(hpjj)==0:
                    break
        ans = max(ans, sum(hpjj))

print(ans)

Solution (Python):
N, K = [int(_) for _ in input().split()]
V = [int(_) for _ in input().split()]

result = 0
for i in range(min(N + 1, K + 1)):
    for j in range(min(N - i + 1, K - i + 1)):
        xs = V[:i] + (V[-j:] if j else [])
        t = sum(xs)
        l = K - i - j
        xsm = list(sorted(x for x in xs if x < 0))[:l]
        r = t - sum(xsm)
        
        result = max(result, r)

print(result)

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

from heapq import heappush, heappop
for i in range(1, k+1):
  for j in range(0, i+1):
    minus = []
    l = min(n, j)
    r = min(n-l, i-l)
    cur = 0
    for ll in range(l):
      cur += v[ll]
      if v[ll]<0:
        heappush(minus, v[ll])
    for rr in range(r):
      cur += v[n-rr-1]
      if v[n-rr-1]<0:
        heappush(minus, v[n-rr-1])
    rm = k-l-r
    while rm>0 and len(minus)>0:
      rm -= 1
      cur -= heappop(minus)
    ans = max(ans, cur)
print(ans)

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

from heapq import heappush, heappop
for i in range(1, k+1):
  for j in range(1, i+1):
    for k in range(0, j+1):
      minus = []
      l = min(n, k)
      r = min(n-l, j-l)
      cur = 0
      for ll in range(l):
        cur += v[ll]
        if v[ll]<0:
          heappush(minus, v[ll])
      for rr in range(r):
        cur += v[n-rr-1]
        if v[n-rr-1]<0:
          heappush(minus, v[n-rr-1])
      rm = i-l-r
      while rm>0 and len(minus)>=rm:
        rm -= 1
        t = heappop(minus)
        cur -= t
      ans = max(ans, cur)
print(ans)

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

ans = 0
A = 0
while A <= min(K, N):
    B = 0
    lst2 = []
    while B <= min(K, N) - A:
        lst2 = lst[:A]+lst[N-B:]
        lst2.sort()
        count = 0
        for i in range(len(lst2)):
            if lst2[i] <= 0 and i+1 <= K - A - B:
                pass
            else:
                count += lst2[i]
        ans = max(ans, count)
        B += 1
    A += 1

print (ans)

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

ans = 0
for lr in range(min(n, k)+1):
    for l in range(lr+1):
        r = lr - l
        jewels = v[:l]+v[-r:] if r > 0 else v[:l]
        n_release = k - lr
        ans_cur = 0
        for j in sorted(jewels):
            if j < 0 and n_release > 0:
                n_release -= 1
            else:
                ans_cur += j
        ans = max(ans, ans_cur)
        
print(ans)

Solution (Python):
from collections import deque, _heapq
N, K = map(int, input().split())
V = deque(map(int, input().split()))

class Money:
    def __init__(self):
        self.yen = 0
        self.red = []

    def value(self):
        return self.yen + sum(self.red)

    def add(self, yen):
        if yen >= 0:
            self.yen += yen
        else:
            self.red.append(yen)

    def remove(self, yen):
        if yen >= 0:
            self.yen -= yen
        else:
            self.red.remove(yen)


def get(cnt, mny, lstop, rstop):
    ans = mny.value()

    if cnt <= 0:
        return ans

    if len(V) > 0:

        if not lstop:
            w = V.popleft()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, lstop, rstop))
            mny.remove(w)
            V.appendleft(w)

        if not rstop:
            w = V.pop()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, True, rstop))
            mny.remove(w)
            V.append(w)

    if len(mny.red) > 0:
        w = min(mny.red)
        mny.red.remove(w)

        V.appendleft(w)
        ans = max(ans, get(cnt-1, mny, True, True))
        V.popleft()

        mny.red.append(w)    

    return ans

print(get(K, Money(), 0, 0))

Solution (Python):
n,k = map(int,input().split())
V = list(map(int,input().split()))
rV = V[::-1]
m = min(n,k)
res = []
for i in range(m+1):
    for j in range(m-i+1):
        Q = []
        Q.extend(V[:i])
        Q.extend(rV[:j])
        if not Q:
            continue
        s = sum(Q)
        Q.sort()
        for p in range(min(len(Q),k-len(Q))):
            if Q[p] < 0:
                s -= Q[p]   
        res.append(s)
print(max(res))

Solution (Python):
N,K = map(int,input().split())
V = list(map(int,input().split()))
W = [0]*N
aplus = [0]
bplus = [0]
anslist = []
for i in range(min(N,K)):
    aplus.append(aplus[i]+V[i])
    bplus.append(bplus[i]+V[N-i-1])
for i in range(min(N+1,K+1)):
    minuslist = []
    for l in range(i+1):
        if (l > 0)&(V[l-1] < 0):
            minuslist.append(V[l-1])
    for j in range(min(N-i+1,K+1)):
        if i + j > K:
            break
        if (j > 0)&(V[-j] < 0):
            minuslist.append(V[-j])
        minuslist.sort()
        if K-i-j > len(minuslist):
            anslist.append(aplus[i]+bplus[j]-sum(minuslist))
        else:
            minus = 0
            anslist.append(aplus[i]+bplus[j])
            for k in range(K-i-j):
                minus += minuslist[k]
                anslist.append(aplus[i]+bplus[j]-minus)
print(max(anslist))

Solution (Python):
def subsolve(pop, push):
    ans = 0
    for i in range(pop + 1):
        rpop, lpop = i, pop - i
        r = [] if rpop == 0 else vs[-rpop:]
        l = [] if lpop == 0 else vs[:lpop]
        ans = max(ans, sum(sorted(r + l)[push:]))
    return ans


NEGINF = -float("inf")
n, k = map(int, input().split())
vs = list(map(int, input().split()))
ans = 0

for k_ in range(k + 1):
    for i in range(k_ + 1):
        push, pop = i, k_ - i
        if push > pop or pop > n:
            continue
        ans = max(ans, subsolve(pop, push))


print(ans)

Solution (Python):
N, K = map(int, input().split())
V = list(map(int, input().split()))
s = 0
for i in range(min(K, N)+1):
    r = K - i
    for j in range(i+1):
        k = i - j
        Q = sorted(V[:j] + V[N-k:])
        m = sum([q < 0 for q in Q])
        s = max(s, sum(Q[min(m, r):]))
print(s)

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

def dispose(disposeList, tms):
    disposeList.sort()
    i = 0
    while i < tms:
        if disposeList[i] < 0:
            disposeList[i] = 0
            i += 1
        else:
            return disposeList
        
    return disposeList
    
res = 0
for take in range(min(N,K)+1):
    for left in range(take+1):
        right = take - left
        my_V = [V[i] for i in range(left)] + [V[-i-1] for i in range(right)]
    
        my_V = dispose(my_V, min(take, K-take))
        res = max(res, sum(my_V))
        
print(res)

Solution (Python):






import sys


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












"""
6 4
-10 8 2 1 2 6
"""





ans = 0
for l in range(K+1):
    if l > N:
        continue
    for r in range(K+1-l):
        if l+r>K or l+r>N:
            continue
        d = K-(l+r)
        picked = V[:l] + V[-r:] if r != 0 else V[:l]
        
        sp = sorted(picked)
        now = sum(picked)
        
        for i in range(d):
            if i >= len(picked):
                break
            if sp[i] > 0:
                break
            now -= sp[i]
        ans = max(ans, now)
print(ans)
        
"""
if N < K:
    scs = []
    for i in range(K-N):
        scs.append(sorted(V[i:]))
    s = max(scs)
else:
    scs = []
    for i in range(K//2):
        
        scss = []
        for j in range(K+1-i):
            
            if j == K-i:
                choices = V[:j]
            else:
                choices = V[:j] + V[-K+j+i:]
            
            
            scss.append(sum(sorted(choices)[i:]))
        scs.append(max(scss))
    s = max(scs)
    s = 0 if s<0 else s
print(s)
"""

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

if K <= 2:
    print(max(V[0], V[-1], 0))
    quit()


ans = 0
for a in range(min(N, K)+1):
    for b in range(min(N-a, K-a)+1):
        V_ = sorted(V[:a] + V[-b:]) if b >= 1 else sorted(V[:a])
        tmp = K - (a+b)
        curMinus = 0
        for v in V_:
            if v < 0 and tmp > 0:
                tmp -= 1
                curMinus += -v
        ans = max(ans, sum(V_)+curMinus)

print(ans)

Solution (Python):
N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for a in range(min(N, K) + 1):
    for b in range(min(N, K) + 1 - a):
        juels = sorted(V[:a] + V[len(V)-b:])
        if not juels:
            continue
        cd = K - a - b
        now = sum(juels)
        for i in range(min(len(juels), cd)):
            if juels[i] < 0:
                now -= juels[i]
        ans = max(ans, now)
print(ans)

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

ans = -10**9
R = min(N, K)
A = R
for a in range(0, A+1):
    B = R-a
    for b in range(0, B+1):
        if b>0:
            v = V[:a] + V[-b:]
        else:
            v = V[:a]
        
        v.sort()
        
        cnt = 0
        for vv in v:
            if vv<0:
                cnt += 1
            else:
                break
        ans = max(ans, sum(v[min(K-a-b, cnt):]))
        
print(ans)

Solution (Python):
[input_n, input_k] = map(int, input().split())

input_v = list(map(int, input().split()))

max_value = 0

for a in range(min(input_n, input_k) + 1):
    for b in range(min(input_n, input_k) - a + 1):
        if (b != 0):
            hold_jewelries = input_v[:a] + input_v[-b:]
        else:
            hold_jewelries = input_v[:a]
        hold_jewelries = sorted(hold_jewelries)

        remove_length = input_k - a - b
        hold_minus = sum(1 for value in hold_jewelries if value < 0)

        hold_value = sum(hold_jewelries[min(hold_minus, remove_length):])

        if (hold_value > max_value):
            max_value = hold_value

print(max_value)

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

m = k // 2 + (k % 2)

a = [0] * (n+1)
d = [0] * (n+1)

a[0] = 0
d[0] = 0
for i in range(n):
    a[i+1] = a[i] + v[i]
    d[i+1] = d[i] + v[n-1-i]

w = []
for i in range(n):
    w.append([v[i], i])

w.sort()

ans = 0

p = min(n, k)
for L in range(p + 1):
    for R in range(p + 1 - L):
        
        temp = a[L] + d[R]
        b = min(L + R, k - L - R)
        c = 0
        while b > 0:
            if w[c][0] >= 0:
                break
            if w[c][1] < L or w[c][1] > n - 1 - R:
                
                temp -= w[c][0]
                b -= 1
            c += 1
        
        ans = max(ans, temp)

print(ans)

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

def solve():
  n,k = (int(i) for i in input().split())
  v = list(int(i) for i in input().split())
  ans = 0
  
  for atimes in range(min(n,k+1)):
    for btimes in range(min(n-atimes+1,k-atimes+1)):
      if [atimes,btimes] == [0,0]:continue
      
      getjewel = v[0:atimes]+v[n-btimes::]
      
      getjewel.sort()
      deletevalue = 0
      maxdeletetimes = k-atimes-btimes
      
      for i in range(min(len(getjewel),maxdeletetimes)):
        if getjewel[i] <= 0:
          deletevalue -= getjewel[i]
      ans = max(sum(getjewel)+deletevalue,ans)
  print(ans)
solve()

Solution (Python):
n,k=map(int,input().split())
v=[int(i) for i in input().split()]
ans=[]

for i in range(min(n,k)+1):
    for j in range(min(n,k)-i+1):
        d=k-i-j
        l=v[0:i]
        r=v[n-j:n]
        p=r+l
        q=[]
        s=sum(p)
        for x in p:
            if x<0:
                q.append(x)
        q.sort()
        for x in range(min(len(q),d)):
            s-=q[x]
        ans.append(s)
        
print(max(ans))

Solution (Python):
n,k = map(int, input().split())
v = list(map(int, input().split()))
t = min(n,k)
ans = 0
for i in range(t+1):
  for j in range(t-i+1):
    hnd = v[:i]+v[-j:]*(j!=0)
    hnd.sort(reverse=True)
    for _ in range(min(k-i-j,len(hnd))):
      if hnd[-1] < 0:
        hnd.pop()
      else:
        break
    cur = sum(hnd)
    if ans<cur:
      ans=cur
print(ans)

Solution (Python):
n,k = map(int,input().split())
V = list(map(int,input().split()))
rV = V[::-1]
Q = []
m = min(n,k)
res = []
for i in range(m+1):
    for j in range(m-i+1):
        Q.extend(V[:i])
        Q.extend(rV[:j])
        if not Q:
            continue
        s = sum(Q)
        Q.sort()
        for p in range(min(len(Q),k-len(Q))):
            if Q[p] < 0:
                s -= Q[p]   
        res.append(s)
        Q = []
print(max(res))

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
	
def main():
	N, K = map(int, input().split(" "))
	V = list(map(int, input().split(" ")))
	
	V_tmp = copy.deepcopy(V)
	ans = 0
	for L in range(K+1):
		for R in range((K+1)-L):
			V = copy.deepcopy(V_tmp)
			gets = []
			tmp = 0
			
			for i in range(L):
				if len(V) > 0:
					tmptmp = V.pop(0)
					tmp += tmptmp
					if tmptmp < 0:
						gets.append(tmptmp)
					
			for i in range(R):
				if len(V) > 0:
					tmptmp = V.pop(-1)
					tmp += tmptmp
					if tmptmp < 0:
						gets.append(tmptmp)
					
			
			for i in range(K-L-R):
				if len(gets) == 0:
					break
				gets.sort()
				tmp = tmp + (-1 * gets.pop(0))
				
			if tmp > ans:
				ans = tmp
				
	print(ans)
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):
import sys
inputs = sys.stdin.readline
N, K= map(int,inputs().split())
V = list(map(int,inputs().split()))

maxim = 0
if K <= 2*N - 1:
	for i in range(0,K+1):
		for j in range(i+1):
			if j == i:
				a = V[:j] + [0]
			else:
				a = V[:j] + V[j-i:] + [0]
			a.sort()
			b = a.index(0)
			if b <= K - i:
				maxim = max(sum(a[b:]),maxim)
			else:
				maxim = max(sum(a[K-i:]),maxim)
else:
	V.append(0)
	V.sort()
	maxim = sum(V[V.index(0):])
print(maxim)

Solution (Python):

N,K=map(int,raw_input().split())
V=map(int,raw_input().split())
VR=list(reversed(V))
ans=-10**8
for l in range(K+1):
    for r in range(K+1):
        if l+r>K or l+r>N:continue
        d=K-l-r
        buf=V[:l]; buf+=VR[:r]
        buf.sort()
        buf.reverse()
        for i in range(d):
            if len(buf)>0 and buf[-1]<0:buf.pop()
        ans=max(ans,sum(buf))
print(ans)

Solution (Python):
from collections import deque, _heapq
N, K = map(int, input().split())
V = deque(map(int, input().split()))

class Money:
    def __init__(self):
        self.yen = 0
        self.red = []

    def value(self):
        return self.yen + sum(self.red)

    def add(self, yen):
        if yen >= 0:
            self.yen += yen
        else:
            self.red.append(yen)

    def remove(self, yen):
        if yen >= 0:
            self.yen -= yen
        else:
            self.red.remove(yen)


def get(cnt, mny, lstop, rstop):
    ans = mny.value()

    if cnt <= 0:
        return ans

    if len(V) > 0:

        if not lstop:
            w = V.popleft()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, lstop, rstop))
            mny.remove(w)
            V.appendleft(w)

        if not rstop:
            w = V.pop()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, True, rstop))
            mny.remove(w)
            V.append(w)

    if len(mny.red) > 0:
        w = min(mny.red)
        mny.red.remove(w)

        V.appendleft(w)
        ans = max(ans, get(cnt-1, mny, True, True))
        V.popleft()

        mny.red.append(w)    

    return ans

print(get(K, Money(), 0, 0))