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 main():
    import copy
    n,k = map(int,input().split())
    v = list(map(int,input().split()))
    ans = 0
    for i in range(min(n+1,k+1)):
        t = v[0:i]
        for j in range(min(n-i+1,k-i+1)):
            t_ = copy.deepcopy(t)
            t_ += v[n-j:n]
            
            r = k-i-j
            t_ = sorted(t_)
            cnt = 0
            for l in range(len(t_)):
                if t_[l]<0 and cnt<r:
                    t_[l] = 0
                    cnt += 1
                else:
                    break
            if ans<sum(t_):
                ans = sum(t_)
    print(ans)

if __name__ == "__main__":
    main()

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)-a+1):
        c = v[:a] + v[n-b:]
        c = sorted(c)
        for i in range(k-a-b):
            if len(c) == 0:
                break
            if c[0] < 0:
                c = c[1:]
            else:
                break
        ans = max(ans,sum(c))
print(ans)

Solution (Python):
n, k = map(int, input().split())
v = list(map(int, input().split()))
m = min(n, k)
max_score = 0
for i in range(m+1):
    for j in range(m+1-i):
        vals = v[:i] if j == 0 else v[:i] + v[-j:]
        minus = list(filter(lambda x : x < 0, vals))
        minus.sort()
        score = sum(vals) - sum(minus[:min(k - i - j, len(minus))])
        if max_score < score:
            max_score = score
print(max_score)

Solution (Python):
import copy

def insert_to_sorted_list(vals:list, new_val):
    l = 0
    r = len(vals)
    while l < r:
        m = (l + r) // 2
        if vals[m] == new_val:
            vals.insert(m, new_val)
            return
        elif vals[m] < new_val:
            l = m + 1
        else:
            r = m
    vals.insert(l, new_val)
    return

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

sum_l = [0] * (n + 1)
sum_r = [0] * (n + 1)
for i in range(1, n+1):
    sum_l[i] += sum_l[i - 1] + v[i - 1]
    sum_r[i] += sum_r[i - 1] + v[n - i]
max_score = -10000000
left_vals = []
left_minus_n = 0
for i in range(0, n + 1):
    if i > k:
        break
    if i > 0:
        if v[i-1] < 0:
           left_minus_n += 1
        insert_to_sorted_list(left_vals, v[i-1])
    vals = copy.copy(left_vals)
    minus_n = left_minus_n
    for j in range(0, n + 1 - i):
        if i + j > k:
            break
        if j > 0:
            if v[n-j] < 0:
                minus_n += 1
            insert_to_sorted_list(vals, v[n-j])
        score = sum_l[i] + sum_r[j]
        score -= sum(vals[0:min(k - i - j, minus_n)])
        if max_score < score:
            max_score = score
print(max_score)

Solution (Python):
N,K = map(int,input().split())
V = list(map(int,input().split()))
vmax = 0
for i in range(K+1):
    for j in range(K-i+1):
        cnt = sum(V[:j])
        A = V[:j]
        n = N-(K-i-j)
        if n>=j:
            cnt += sum(V[n:])
            A += V[n:]
        else:
            cnt += sum(V[j:])
            A += V[j:]
        A = sorted(A)
        B = []
        for k in range(i):
            if k<len(A) and A[k]<0:
                B.append(k)
        for k in B:
            cnt -= A[k]
        vmax = max(vmax,cnt)
print(vmax)

Solution (Python):
def solve():
  ans = 0
  N, K = map(int, input().split())
  V = list(map(int, input().split()))
  A = V[:]*2
  for k in range(K,-1,-1): 
    if k>=N:
      suteru = k-N
      a = V[:]
      a.sort()
      ans = max(ans,sum(a[suteru:]))
    else:
      for i in range(k//2+1,k+1): 
        suteru = k-i
        for j in range(i+1):
          a = A[N-j:N+i-j]
          a.sort()
          ans = max(ans,sum(a[suteru:]))
  return ans
print(solve())

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

from collections import deque
V = deque(V)

import copy

ans = -10**18
for i in range(k+1):
    for j in range(k+1):
        if i+j > k:
            continue
        if i+j > n:
            continue
        V_ = copy.copy(V)
        temp = []
        for p in range(i):
            temp.append(V_.popleft())
        for q in range(j):
            temp.append(V_.pop())
        temp.sort()
        s = sum(temp)
        l = k-i-j
        for r in range(min(l, len(temp))):
            if temp[r] < 0:
                s -= temp[r]
        ans = max(ans, s)
print(ans)

Solution (Python):
def solve():
  ans = 0
  N, K = map(int, input().split())
  V = list(map(int, input().split()))
  A = V[:]*2
  for k in range(K,-1,-1): 
    if k>=N:
      suteru = k-N
      a = V[:]
      a.sort()
      ans = max(ans,sum(a[suteru:]))
    else:
      for i in range(k//2+1,k+1): 
        suteru = k-i
        for j in range(i+1):
          a = A[N-j:N+i-j]
          a.sort()
          ans = max(ans,sum(a[suteru:]))
  return ans
print(solve())

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
V = rl()
dp = [[[-float('inf')]*(K+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
	for j in range(N):
		for k in range(K):
			dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k])
			
			
			
			
			ni, nj, nk = i+1, j, k+1
			if ni+nj <= N:
				dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k]+V[i])
				if V[i] < 0 and nk+1 <= K:
					dp[ni][nj][nk+1] = max(dp[ni][nj][nk+1], dp[i][j][k])
			ni, nj, nk = i, j+1, k+1
			if ni+nj <= N:
				dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k]+V[N-j-1])
				if V[N-j-1] < 0 and nk+1 <= K:
					dp[ni][nj][nk+1] = max(dp[ni][nj][nk+1], dp[i][j][k])

ans = 0
for i in range(N+1):
	for j in range(N+1):
		ans = max(ans, dp[i][j][K])
print(ans)

Solution (Python):
import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    ans = 0

    for i in range(min(N + 1, K+1)):  
        for j in range(min(N + 1 - i, K - i+1)):  
            res = K - i - j  
            agg = V[:i] + V[N  - j:]
            agg.sort(reverse=True)
            while res > 0 and agg:
                if agg[-1] < 0:
                    agg.pop()
                    res -= 1
                else:
                    break
            ans = max(sum(agg), ans)
    print(ans)


if __name__ == "__main__":
    main()

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

res = 0
r = min(n, k)
for i in range(r+1):
    for j in range(r-i+1):
        in_hand = v[:i] + v[n-j:] if i + j < n else v[:]
        in_hand.sort(reverse=True)
        for _ in range(k-len(in_hand)):
            if not in_hand or in_hand[-1] >= 0:
                break
            in_hand.pop()
        res = max(res, sum(in_hand))
print(res)

Solution (Python):
from itertools import accumulate
n, k = map(int, input().split())
vs = list(map(int, input().split()))
res = 0
for i in range(min(n,k)+1):
    for j in range(min(n-i,k-i)+1):
        res_tmp = 0
        arr = []
        if i > 0:
            arr += vs[:i]
        if j > 0:
            arr += vs[(n-j):]
        if arr != []:
            arr.sort()
            n_len = len(arr)
            for m in range(min(k-i-j,n_len)):
                if arr[m] >= 0:
                    break
                res_tmp -= arr[m]
            res_tmp += sum(arr)
        res = max(res,res_tmp)
print(res)

Solution (Python):
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(k+1):
  for j in range(k+1):
    if i+j > k or i+j > n:
      continue
    t = k-(i+j)
    s = v[:i] + v[(n-j):]
    s.sort()
    u = 0
    while u < t:
      u += 1
      if len(s) < 1:
        break
      if s[0] < 0:
        s.pop(0)
      else:
        break
    ans = max(ans, sum(s))
print (ans)

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

ans = 0
for i in range(min(n,k)+1):
    for j in range(min(n,k)-i+1):
        l = [0]
        r = [0]
        mm = [0]
        for p in range(i):
            if v[p] > 0:
                l.append(v[p])
            else:
                heapq.heappush(mm,v[p])
        for o in range(j):
            if v[-o-1] > 0:
                r.append(v[-o-1])
            else:
                heapq.heappush(mm,v[-o-1])
        for m in range(min(k-i-j,len(mm))):
            heapq.heappop(mm)
        ans = max(ans,sum(l)+sum(r)+sum(mm))
print(ans)

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

ans = 0
for i in range(min(n,k)+1):
    for j in range(min(n,k)-i+1):
        l = [0]
        r = [0]
        mm = [0]
        for p in range(i):
            if v[p] > 0:
                l.append(v[p])
            else:
                heapq.heappush(mm,v[p])
        for o in range(j):
            if v[-o-1] > 0:
                r.append(v[-o-1])
            else:
                heapq.heappush(mm,v[-o-1])
        for m in range(min(k-i-j,len(mm))):
            heapq.heappop(mm)
        
        ans = max(ans,sum(l)+sum(r)+sum(mm))
print(ans)

Solution (Python):
from heapq import heapify, heappop, heappush

N, K = map(int, input().split())
V = list(map(int, input().split()))
INF = 10**9

def h(X, cnt):
  S = sum(X)
  heapify(X)
  limit = cnt
  while cnt < K and cnt < 2*limit:
    m = heappop(X)
    if m >= 0:
      break
    S -= m
    cnt += 1
  return S

ans = 0

for i in range(1, min(N, K)+1):
  if i != N:
    for j in range(i+1):
      X = V[:i-j] + V[N-j:]
      ans = max(ans, h(X, i))
  else:
    ans = max(ans, h(V, i))

print(ans)

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

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

    
    ans = 0
    R = min(N,K)

    for i in range(R+1):
        for j in range(R+1-i):
            tmp = 0
            q = []
            
            for k in range(i):
                tmp += V[k]
                if V[k] < 0:
                    q.append(V[k])
            for k in range(j):
                tmp += V[N-1-k]
                if V[N-1-k] < 0:
                    q.append(V[N-1-k])

            q.sort()
            tmp -= sum(q[:min(len(q),K-i-j)])
            ans = max(ans,tmp)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq
pop = heapq.heappop
push = heapq.heappush

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

ans = 0
for i in range(min(N + 1, K + 1)):
  for j in range(min(N + 1, K + 1) - i):
    q = []
    t = 0
    for k in range(i):
      tt = V[k]
      t += tt
      push(q, tt)
    for k in range(j):
      tt = V[N - 1 - k]
      t += tt
      push(q, tt)

    for k in range(K - i - j):
      if q == []:
        break
      tt = pop(q)
      if tt >= 0:
        break
      t -= tt

    ans = max(ans, t)
print(ans)

Solution (Python):







__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


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

  max_ = 0
  for i in range(N+1):
    for j in range(N+1):
      res = K-(i+j)
      if i+j == 0 or i+j > N or K-(i+j) < 0:
        continue
      temp = sorted(V[:i]+V[-j if j else len(V):])
      start = 0
      for k in range(min(res, len(temp))):
        if temp[k] < 0:
          start += 1
      max_ = max(max_, sum(temp[start:]))
      
      
      
      

  print(max_)


if(__name__ == '__main__'):
  main()

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

ans = 0
for x in range(k+1):
  for y in range(k-x+1):
    temp = v[:x]+v[len(v)-y:]
    if x+y >= n:
      temp = v
    temp1 = []
    temp2 = []
    for i in temp:
      if i >= 0:
        temp1.append(i)
      else:
        temp2.append(i)

    temp2.sort()
    ans = max(ans, sum(temp1) + sum(temp2[k-x-y:]))
print(ans)

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

ans = 0
for x in range(k+1):
  for y in range(k-x+1):
    temp1 = []
    temp2 = []
    if x+y >= n:
      for i in v:
        if i >= 0:
          temp1.append(i)
        else:
          temp2.append(i)
    else:
      for i in v[:x]:
        if i >= 0:
          temp1.append(i)
        else:
          temp2.append(i)
      for i in v[len(v)-y:]:
        if i >= 0:
          temp1.append(i)
        else:
          temp2.append(i)
    temp2.sort()
    ans = max(ans, sum(temp1) + sum(temp2[k-x-y:]))
print(ans)

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

max_value = -10**9
for kL in range(0, K+1):
    for kR in range(0, K+1):
        if kL + kR > min(N, K):
            continue
        vL = V[:kL]
        vR = []
        if kR:
            vR = V[-kR:]
        hand = list(sorted(vL + vR, reverse=True))
        rest = K - (kL + kR)
        for kD in range(rest):
            if len(hand) == 0:
                break
            if hand[-1] < 0:
                hand.pop()
            else:
                break
        value = sum(hand[:K])
        if value > max_value:
            max_value = value
print(max_value)

Solution (Python):
def main():
    n, k = list(map(int, input().split()))
    V = list(map(int, input().split()))
    ans = -1
    for i in range(c := min(n, k) + 1):
        for j in range(c - i):
            A = V[:i] + V[-j:] if j != 0 else V[:i]
            A.sort(reverse = True)
            r = k - (i + j)
            for _ in range(r):
                if len(A) == 0:
                    break
                if (a := A.pop()) >= 0:
                    A.append(a)
                    break
            ans = max(ans, sum(A))
    print(ans)



if __name__ == '__main__':
    main()

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

def main(n,k,v):
    ruisekiL=[0]*(n+1)
    ruisekiR=[0]*(n+1)
    for i in range(1,n+1):
        ruisekiL[i]=ruisekiL[i-1]+v[i-1]
        ruisekiR[i]=ruisekiR[i-1]+v[n-i]
    vv=[]
    for i in range(n):
        vv.append((i+1,v[i]))
    vv.sort(key=lambda x:x[1])
    

    maxown=-10**7
    for kk in range(k+1):
        if n<kk:
            own=ruisekiL[n]
            m=0
            while m<n and vv[m][1]<0: 
                own-=vv[i][1]
                m+=1
            
            maxown=max(maxown,own)
        else:
            for l in range(kk//2+1):
                for i in range(kk-l+1):
                    j=kk-i-l
                    jj=n-j+1
                    own=ruisekiL[i]+ruisekiR[j]
                    
                    m=0
                    mcnt=0
                    while(mcnt<l):
                        if i<vv[m][0] and vv[m][0]<jj:
                            m+=1
                            continue
                        
                        own-=vv[m][1]
                        mcnt+=1
                        m+=1
                    
                    maxown=max(own,maxown)
    return maxown

def main2(n,k,v):
    ruisekiL=[0]*(n+1)
    ruisekiR=[0]*(n+1)
    for i in range(1,n+1):
        ruisekiL[i]=ruisekiL[i-1]+v[i-1]
        ruisekiR[i]=ruisekiR[i-1]+v[n-i]
    vv=[]
    for i in range(n):
        vv.append((i+1,v[i]))
    vv.sort(key=lambda x:x[1])
    

    maxown=-10**7
    for i in range(n+1):
        for j in range(n+1):
            if i+j>k or i+j>n:
                break
            jj=n-j+1
            own=ruisekiL[i]+ruisekiR[j]
            
            l=min(i+j,k-i-j)
            m=0
            mcnt=0
            while(mcnt<l):
                if i<vv[m][0] and vv[m][0]<jj:
                    m+=1
                    continue
                if vv[m][1]>=0:
                    break
                own-=vv[m][1]
                mcnt+=1
                m+=1
            
            maxown=max(own,maxown)
    return maxown

if __name__=='__main__':
    n,k,v=readinput()
    ans=main2(n,k,v)
    print(ans)

Solution (Python):
N, K = map(int, input().split())
V = [0]*N
*V, = map(int, input().split())

ans = []
for i in range(N+1):
    for j in range(N+1):
        if i+j > min(N, K): continue
        out = V[:i] + V[N-j:]
        out.sort()
        r = 0
        while i+j+r < K and r < len(out):
            if out[r] < 0: r += 1
            else: break
        ans.append(sum(out[r:]))

print(max(ans))

Solution (Python):
from collections import deque
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(1, min(n, k+1)):
    vv = deque(v)
    q = deque(v[:i])
    for _ in range(i+1):
        tmp = list(q)
        tmp.sort()
        rem = k-i
        s = sum(tmp)
        for j in tmp:
            if rem==0 or j>=0:
                break
            s -= j
            rem -= 1
        ans = max(ans, s)
        q.pop()
        q.appendleft(vv.pop())
if k>=n:
    v.sort()
    rem = k-n
    s = sum(v)
    for j in v:
        if rem==0 or j>=0:
            break
        s -= j
        rem -= 1
    ans = max(ans, s)
print(ans)

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

for i in range(1, K + 1):
  nownow = 0
  for p in range(i + 1):
    
    if i < N:
      now = sorted(V[:p] + V[p + N - i:])
    else:
      now = V
    
    index = bisect.bisect_right(now, 0)
    
    if K - i >= index:
      nownow = sum(now[index:])
    else:
      nownow = sum(now[K - i:])
    ans = max(ans, nownow)
    

print(ans)

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








ans = 0

for i in range(K + 1):
    for j in range(K - i + 1):
        
        
        
        for k in range(K - i - j + 1):
            if i + j < N:
                left_nums = values[0:i].copy()
                right_nums = values[N - j:N].copy()
                nums = sorted(left_nums + right_nums)
                ans = max(ans, sum(nums[k:]))
            elif i + j == N:
                nums = sorted(values.copy())
                ans = max(ans, sum(nums[k:]))
            else:
                if k < N - (i + j):
                    continue
                nums = sorted(values.copy())
                ans = max(ans, sum(nums[k - (N - (i + j)):]))


print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    
    N, K = map(int, input().split())
    
    vs = tuple(map(int, input().split())) 
    
    
    ans=0
    ls=0
    dlis1=[]
    for l in range(min(N,K)+1):
        rs=0
        dlis2=[]
        if l>=1:
            tag=vs[l-1]
            ls+=tag
            if tag<0:
                dlis1.append(tag)
        for r in range(min(K-l,N)+1):
            if r>=1:
                tag=vs[-1-r+1]
                rs+=tag
                if tag<0:
                    dlis2.append(tag)
            dlis=dlis1+dlis2
            dlis.sort()
            td=0
            
            dec =min(K-l-r,len(dlis))
            if dec>=1:
                td=sum(dlis[:dec])
            tot=ls+rs-td
            
            ans=max(ans,tot)

            if l+r>=N:
                break

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq
import itertools
def main():
    n,k=map(int, input().split())
    v=[int(i) for i in input().split()]
    
    v_1 = v[::-1]
    
    
    res = 0
    for i in range(k+1):
        j = 0
        while(i+j<=min(n,k)):

            q = []
            tmp = 0
            if(i>0):
                for l in range(i):
                    if(v[l]<0):
                        heapq.heappush(q,v[l])
                    tmp += v[l]
            if(j>0):
                for l in range(j):
                    if(v_1[l]<0):
                        heapq.heappush(q,v_1[l])
                    tmp += v_1[l]
            for l in range(k-(i+j)):
                if(len(q)>0):
                    z = heapq.heappop(q)
                    tmp -= z
            j+=1
            res = max(res,tmp)

    print(res)
if __name__ == '__main__':
    main()

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

ans = - 10 ** 19

for i in range(min(k + 1, n + 1)):
  
  for j in range(i + 1):
    inhands = V[:j] + V[n - i + j:]
    inhands.sort()
    remnum = k - i
    val = 0
    for h in inhands:
      if h < 0 and remnum > 0:
        remnum -= 1
      else:
        val += h
    ans = max(ans, val)
print(ans)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)



class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


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

ans = -INF
for i in range(k + 1):
    for j in range(k + 1):
        if i + j > k or i + j > n:
            continue
        x = v[:i] + v[n - j:]
        x.sort()
        cnt = sum(x)
        for l in range(min(k - i - j, i + j)):
            if x[l] >= 0:
                break
            cnt -= x[l]
        ans = max(ans, cnt)
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, K = getNM()
V = getList()

V = 2 * V

ans = 0
for i in range(1, min(K + 1, N + 1)):
    slow = K - i
    for j in range(N - i, N + 1):
        opt = sorted(V[j: j + i])
        for l in range(min(len(opt), slow)):
            if opt[l] < 0:
                opt[l] -= opt[l]
        ans = max(ans, sum(opt))
print(ans)

Solution (Python):
import heapq
from collections import deque
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
        p = v[:]
        d = deque(p)
        a = []
        heapq.heapify(a)
        for t in range(i):
            heapq.heappush(a,d.popleft())
        for l in range(j):
            heapq.heappush(a,d.pop())
        nokori = k-i-j
        for s in range(nokori):
            if a:
                now = heapq.heappop(a)
                if now > 0:
                    heapq.heappush(a,now)
                    break
            else:
                break
        ans = max(ans,sum(a))
print(ans)

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

ans = -1

for l in range(N+1):
    for r in range(N+1):
        tmp = V[:l] + V[N-r:]
        if l+r > N:
            break
        res = K - (l+r)
        if res < 0:
            break
        tmp.sort()
        for i in range(min(res,len(tmp))):
            if tmp[0] < 0:
                tmp.pop(0)
            else:
                break
        ans = max(ans,sum(tmp))
            
print(ans)