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):
N, K = map(int, input().split())
V = [int(i) for i in input().split()]
ans = 0
for M in range(K+1):
    for m in range(M+1):
        ls = []
        for i, x in enumerate(V):
            if i < m:
                ls.append(x)
        for i, x in enumerate(V[::-1]):
            if i < min(M-m, N-m):
                ls.append(x)
        ls.sort()
        s = sum(ls)
        for i, x in enumerate(ls):
            if i < K-M and x < 0:
                s -= x
        ans = max(ans, s)
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


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 make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,K = IL()
V = IL()

def dig(L,d):
  N = len(L)
  dic = [[0,[]]]
  for l in L:
    if l>=0:
      dic.append([dic[-1][0]+l,dic[-1][1]])
    else:
      dic.append([dic[-1][0],dic[-1][1]+[l]])
  MAX = 0
  for i in range(N+1):
    dic[i][1].sort(reverse=True)
  for i in range(d+1):
    i = min(i,N)
    MAX = max(MAX,dic[i][0]+sum(dic[i][-1][:max(0,len(dic[i][-1])-(d-i))]))
  return MAX
  
MAX = 0
for i in range(N+1):
  for k in range(K+1):
    MAX = max(MAX,dig(V[:i],k)+dig(V[i:][::-1],K-k))
  
print(MAX)

Solution (Python):
from bisect import bisect_left, bisect_right

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

ans = 0
for get_num in range(0,k+1):
    rem = k-get_num
    for l in range(0,get_num+1):
        r = get_num-l
        if l+r > n: continue
        ls = vl[:l]
        rs = vl[n-r:]
        curr_l = ls + rs
        curr_l.sort()
        minus_cnt = bisect_left(curr_l, 0)
        if minus_cnt <= rem:
            curr_ans = sum(curr_l[minus_cnt:])
            ans = max(curr_ans,ans)
        else:
            curr_ans = sum(curr_l[rem:])
            ans = max(curr_ans,ans)

print(ans)

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

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

res = 0

for i in range(n+1):
    for j in range(n-i+1):
        if k < i+j:
            continue
        memo = v[:i] + v[n-j:]
        memo.sort()

        for _ in range(k-i-j):
            if memo and memo[0] < 0:
                memo.pop(0)
            else:
                break
        res = max(res,sum(memo))
print(res)

Solution (Python):
import copy

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

ans = 0

for l in range(0,n+1):
    for r in range(0,n+1):
        if l+r > n or l+r > k or l+r==0:
            continue
        vc = copy.deepcopy(v)
        have = []
        ll = copy.deepcopy(l)
        rr = copy.deepcopy(r)
        while ll:
            tmp = vc.pop(0)
            have.append(tmp)
            ll -= 1
        while rr:
            tmp = vc.pop(-1)
            have.append(tmp)
            rr -= 1
        have.sort()
        kk = copy.deepcopy(k)
        while have[0] < 0 and kk-(l+r) > 0:
            tmp = have.pop(0)
            kk -= 1
            if not have:
                break
        ans = max(ans, sum(have))
print(ans)

Solution (Python):
n, k = map(int, input().split())
v = [int(i) for i in input().split()]
ans = 0
for a in range(min(n, k) + 1):
    pa, va = v[:a], v[a:]
    for b in range(min(n, k) - a + 1):
        pb = pa + va[-b:] if b > 0 else pa
        pb.sort()
        s = sum(pb)
        ans = max(s, ans)
        for c in range(min(k - a - b, a + b)):
            s -= pb[c]
            ans = max(s, ans)
print(ans)

Solution (Python):
n,k=map(int,input().split())
*q,=map(int,input().split())

ans=0
for i in range(1,k+1): 
    if i<n:
        for left in range(0,i+1): 
            tmp=0
            tmpq=[]
            right=i-left
            if right==0:
                right=-n
            tmpq+=q[:left]+q[-right:]
            tmp+=sum(tmpq)
            tmpq=[x for x in tmpq if x<0]
            tmpq=sorted(tmpq)
            tmp-=sum(tmpq[:min(k-i, len(tmpq))])
            ans=max(ans,tmp)
    else:
        for left in range(0,n+1):
            tmp=0
            tmpq=[]
            right=n-left
            if right==0:
                right=-n
            tmpq+=q[:left]+q[-right:]
            tmp+=sum(tmpq)
            tmpq=[x for x in tmpq if x<0]
            tmpq=sorted(tmpq)
            tmp-=sum(tmpq[:min(i-n, len(tmpq))])
            ans=max(ans,tmp)
print(ans)

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

ans=0
for i in range(1,min(k,n)+1):
    
    for m in range(i+1):
        s=v[:m]+v[n-(i-m):]
        s.sort()
        
        
        for j in range(i,min(k,2*i)):
            
            if s[j-i]<0:s[j-i]=0
        
        ans=max(ans,sum(s))
        
        
        
        
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque

from heapq import heapify, heappop, heappush



def solve():
    N, K = MI()
    V = LI()
    max_iter = min(N, K)
    ans = 0
    for a in range(max_iter+1):
        left = V[:a]
        for b in range(0, max_iter-a+1):
            right = V[-b:] if b != 0 else []
            k = K - a - b
            
            
            lst = sorted(left + right)
            
            sm = sum(lst)
            l = len(lst)
            for kk in range(1, k+1):
                if kk < l:
                    tmp = lst[kk-1]
                    if tmp >= 0: break
                    sm -= tmp
                    
                else:
                    break
            ans = max(ans, sm)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
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 <= k and i + j <= n:
            g = v[:i] + v[n-j:]
            g.sort()
            for l in range(min(k-i-j, i+j)+1):
                ans = max(ans, sum(g[l:]))

print(ans)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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 power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
v = lr()
v2 = [0]
for i in range(n):
    v2.append(v2[-1]+v[i])
def sumArea(l,r):
    return v2[r]-v2[l]
ans = -inf
for tmp in range(min(k,n)+1):
    for r in range(tmp+1):
        minus = []
        for num in v[:tmp-r]:
            if num < 0:
                minus.append(num)
        for num in v[n-r:]:
            if num < 0:
                minus.append(num)
        pre = sumArea(0,tmp-r) + sumArea(n-r,n)
        l = min(tmp,k-tmp,len(minus))
        if minus:
            minus.sort()
            pre -= sum(minus[:l])
        ans = max(ans,pre)
print(ans)

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

ans = []

for left in range(N + 1):
    for right in range(N + 1):
        if left + right > N:
            break

        li = V[:left] + V[N - right :]
        li = sorted(li)

        d = K - left - right
        if d < 0:
            break

        c = sum(li)
        for i in range(min(d, len(li))):
            if li[i] < 0:
                c -= li[i]
            else:
                break

        ans.append(c)

print(max(ans))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K,*V = map(int,read().split())

vals = []
for L in range(N+1):
    for R in range(N+1):
        if L+R > N:
            break
        get = V[:L] + V[N-R:]
        rest = K - (L+R)
        if rest < 0:
            break
        get.sort(reverse=True)
        for _ in range(min(len(get),rest)):
            if get[-1] < 0:
                get.pop()
            else:
                break
        vals.append(sum(get))

answer = max(vals)
print(answer)

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

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

ans = -float("inf")


for i in range(targ+1):
    
    for j in range(targ+1-i):
        get = sorted(V[:i] + V[N-j:])
        tmp = sum(get)
        for k in range(min(K-i-j, i+j)):
            tmp = max(tmp, tmp-get[k])
        
        ans = max(tmp, ans)

print(ans)

Solution (Python):
n,k=[int(x) for x in input().rstrip().split()]
v=[int(x) for x in input().rstrip().split()]
vr=v[::-1]
ans=0
mi=min(n,k)

for i in range(mi+1):
  for j in range(mi-i+1):
    minus=0
    now=v[:i]+vr[:j]
    d=k-(len(now))
    now.sort()
    md=min(d,len(now))
    for s in range(md):
      if 0<=now[s]:
        break
      minus+=now[s]

    ans=max(ans,sum(now)-minus)
print(ans)

Solution (Python):
import heapq
import copy
N,K = map(int, input().split())
V_list= list(map(int, input().split()))

selected = []
left = []

max_sum = 0
left_sum = 0
for l in range(N):
    selected = copy.deepcopy(left)
    lr_sum = left_sum
    for r in range(N-l+1):
        
        stock = K-l-r
        if stock < 0:
            break
        ri = N-r-1
        select_cnt = len(selected)
        tmp_sum = lr_sum
        max_sum = max(max_sum, tmp_sum)
        popper = copy.deepcopy(selected)

        for i in range(stock):
            if i >= select_cnt:
                break
            
            pop_v = heapq.heappop(popper)
            if pop_v > 0:
                break
            tmp_sum -= pop_v
            max_sum = max(max_sum, tmp_sum)

        r_val = V_list[ri]
        lr_sum += r_val
        heapq.heappush(selected, r_val)

    l_val = V_list[l]
    left_sum += l_val
    heapq.heappush(left, l_val)

print(max_sum)

Solution (Python):

import bisect
import heapq
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
V = list(map(int, input().split()))
V_sorted =sorted(V)



ans =[]
take_V =[] 

if V_sorted[-1] <=0:
    ans =0
else:
    take_num =min(K,N)
    for tak in range(1,take_num +1):
        for lef in range(tak+1):
            
            
                take =[]  
                rig =N-(tak -lef )          
                take.extend(V[    :lef])
                take.extend(V[rig:   ])
                take.sort()
                reverse =min(K -tak,tak) 
                ind_0 =bisect.bisect_left(take,0)
                rev =min(ind_0,reverse,K -tak)
                take_V.append(sum(take[rev:])) 
        
    ans =max(take_V)
print(ans)

Solution (Python):

import bisect
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
V = list(map(int, input().split()))
V_sorted =sorted(V)



ans =[]
take_V =[] 

if V_sorted[-1] <=0:
    ans =0
else:
    take_num =min(K,N)
    for tak in range(1,take_num +1):
        reverse =min(K -tak,tak) 
        for lef in range(tak+1):
            for rev in range(reverse +1):
            
                take =[]                    
                rig =N-(tak -lef )          
                take.extend(V[    :lef])
                take.extend(V[rig:   ])
                take.sort()
                take_V.append(sum(take[rev:]))
        
    ans =max(take_V)
print(ans)

Solution (Python):
n, k = map(int,input().split())
targ = min(n, k)
v = list(map(int,input().split()))
"""
i…左を取る回数
j…右を取る回数
残り回数 k-(i+j)
"""
ans = -10**18
for i in range(targ+1):
	for j in range(targ-i+1):
		
		nl = v[:i] + v[n-j:]
		nl.sort()
		
		tmp = sum(nl)
		for t in range(min(k-(i+j), i+j)):
			tmp = max(tmp, tmp-nl[t])
			
		
		ans = max(tmp, ans)
print(ans)

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):
import sys
from bisect import bisect_left


read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *V = map(int, read().split())

    ans = 0
    for k in range(min(N, K) + 1):
        for left in range(k + 1):
            right = k - left
            tmp = V[:left] + (V[-right:] if right else [])
            tmp.sort()

            idx = bisect_left(tmp, 0)
            if idx > K - k:
                idx = K - k

            this_ans = sum(tmp[idx:])
            if ans < this_ans:
                ans = this_ans

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int,input().split())
V = list(map(int,input().split()))
Vrev = V[::-1]
ans = 0
for a in range(N+1):
    for b in range(min(K-a,N-a)+1):
        VV = V[:a] + Vrev[:b]
        VV.sort(reverse=True)
        for k in range(min(K-a-b,len(VV))):
            if VV[-1] < 0:
                VV.pop()
        ans = max(sum(VV),ans)
print(ans)

Solution (Python):
import sys

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

ans=0
act = min(N, K)
for i in range(act + 1): 
    for j in range(N - act + i, N+1): 
        count = V[0:i] + V[j:N]
        count.sort()
        ans = max(ans, sum(count))
        for x in range(1, K - len(count) + 1): 
            
            ans = max(ans, sum(count[x:]))
print(ans)

Solution (Python):
import heapq

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

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

ans = 0
for i in range(1, K+1):
    if i > N:
        continue
    for j in range(i+1):
        tmp = 0
        q = V[:j] + V[N-i+j:]
        heapq.heapify(q)
        for _ in range(min(i, K-i)):
            tmp_min = heapq.heappop(q)
            ans = max(ans, sum(q))
            if tmp_min > 0:
                ans = max(ans, sum(q)+tmp_min)
                break
        ans = max(ans, sum(q))

print(ans)

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

ans = -(10**9)
for A in range(0,K+1,1):
    for B in range(0,min(K,N)-A+1,1):
        tmp = V[0:A] + V[N-B:N]
        tmp.sort()
        for i in range(0,min(K-A-B,A+B),1):
            tmp[i]=max(tmp[i],0)
        ans = max(ans,sum(tmp))
print(ans)

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

ans = -(10**9)
for A in range(0,K+1,1):
    for B in range(0,min(K,N)-A+1,1):
        tmp = V[0:A] + V[N-B:N]
        tmp.sort()
        for i in range(0,min(K-A-B,A+B),1):
            tmp[i]=max(tmp[i],0)
        ans = max(ans,sum(tmp))
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MAX = min(N, K) + 1

ans = 0
for a in range(MAX):
    for b in range(MAX):
        if a + b >= MAX:
            continue
        jewels = []
        for i in range(a):
            jewels.append(V[i])
        for j in range(b):
            jewels.append(V[-(j + 1)])
        jewels = sorted(jewels)
        total = sum(jewels)
        if K - (a + b) <= 0:
            ans = max(total, ans)
            continue
        for i in range(K - a - b):
            if i < len(jewels) and jewels[i] < 0:
                total += abs(jewels[i])
        ans = max(total, ans)
print(ans)

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


def get_jewelries(box, left_pop, right_pop):
    if left_pop + right_pop >= len(box):
        return box[:]

    left = box[:left_pop]
    right = box[-right_pop:] if right_pop else []

    return left + right


candidates = []
pop_max = min(k, n)
for pop_count in range(pop_max+1):
    residue = k - pop_count

    for left_pop in range(pop_count+1):
        right_pop = pop_count - left_pop
        jewelries = get_jewelries(V, left_pop, right_pop)
        jewelries.sort(reverse=True)

        for _ in range(residue):
            if not jewelries:
                break
            if jewelries[-1] < 0:
                jewelries.pop()

        value = sum(jewelries)
        candidates.append(value)

print(max(candidates))

Solution (Python):
from collections import deque
import heapq
N,K = map(int,input().split())
A = list(map(int,input().split()))
res = 0

for a in range(N+1):
  
  for b in range(N+1):
    if a+b>N or a+b>K: continue
    hands = []
    A1 = deque(A[::])
    for _ in range(a):
      hands.append(A1.popleft())
    for _ in range(b):
      hands.append(A1.pop())
    hands.sort()
    hands = deque(hands)
    rem = K - a - b
    for _ in range(rem):
      if hands and hands[0] < 0:
        hands.popleft()
      else:
        break
    res = max(res, sum(hands))

print(res)

Solution (Python):
import sys
import copy
import heapq
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
INF = 10**9 + 7


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

    ans = -INF
    for n in range(1, N + 1):
        if n > K:
            break
        for rn in range(n + 1):
            ln = n - rn
            tv = copy.copy(V)
            pv = 0
            mv = []
            heapq.heapify(mv)
            for _ in range(rn):
                v = tv.pop()
                if v >= 0:
                    pv += v
                else:
                    heapq.heappush(mv, v)
            for _ in range(ln):
                v = tv.popleft()
                if v >= 0:
                    pv += v
                else:
                    heapq.heappush(mv, v)

            mvlen = min(K - n, len(mv))
            for _ in range(0, mvlen):
                heapq.heappop(mv)

            
            ans = max(ans, pv + sum(mv))

    print(max(0, ans))


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    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):
            if l+r > N or l+r>K:
                continue
            now = []
            val = 0
            for i in range(l):
                now.append(V[i])
                val += V[i]
            for j in range(r):
                now.append(V[-j-1])
                val += V[-j-1]

            d = K-l-r
            now.sort()
            for i in range(d):
                if i >= len(now):
                    break
                if now[i] > 0:
                    break
                val -= now[i]
            ans=max(ans,val)

    print(ans)

resolve()

Solution (Python):

import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    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):
            if l+r > N:
                continue
            now = []
            val = 0
            for i in range(l):
                now.append(V[i])
                val += V[i]
            for j in range(r):
                now.append(V[-j-1])
                val += V[-j-1]

            d = K-l-r
            now.sort()
            for i in range(d):
                if i >= len(now):
                    break
                if now[i] > 0:
                    break
                val -= now[i]
            ans=max(ans,val)

    print(ans)

resolve()

Solution (Python):
from sys import stdin, setrecursionlimit
from bisect import bisect_left


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    v = list(map(int, input().split()))

    ans = 0

    for i in range(1, k + 1):
        if i < n:
            for j in range(i + 1):
                cand = v[: j] + v[n - i + j:]
                cand.sort()
                idx = min(bisect_left(cand, 0), k - i)
                if idx > 0 or i > 0:
                    ans = max(ans, sum(cand[idx:]))

        else:
            cand = v
            cand.sort()
            idx = bisect_left(cand, 0)
            ans = max(ans, sum(cand[idx:]))

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
jewel, query = map(int, input().split())
t = min(jewel, query)
dq = [int(i) for i in input().split()]
ans = []

for i in range(t+1):
  for j in range(i+1):
    have = dq[:j] + dq[(jewel-i+j):]
    drop = query - len(have)

    for k in range(drop):
      if not have:
        break
      
      cand = min(have)
      if cand < 0:
        have.remove(cand)
      else:
        break
        
    ans.append(sum(have))
    
print(max(ans))

Solution (Python):

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

MAX = 0
for k in range(1, K+1):
    for ka in range(k+1):
        for kb in range(k+1-ka):
            kcd = k - ka - kb
            
            if (ka+kb <= kcd) or (ka+kb > N):
                continue
            
            
            s = V[:ka] + V[-kb:] if kb != 0 else V[:ka]
            s.sort()
            
            MAX = max(MAX, sum(s[kcd:]))

print(MAX)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)

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):
        if l+r > n :break

        d=k-l-r
        now=0
        s=[]

        for i in range(l):
            now+=v[i]
            s.append(v[i])

        for i in range(n-r,n):
            now+=v[i]
            s.append(v[i])

        s.sort()
        for i in range(d):
            if(i >= len(s)):break
            if s[i] > 0 :break

            now -= s[i]

        ans=max(now,ans)
print(ans)

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

ans = 0
for left in range(min(n, k+1)):
    for right in range(min(n-left+1, k-left+1)):
        l = v[:left]
        l+=v[::-1][:right]
        l.sort()
        temp = sum(l)
        for t in range(max(0, min(len(l), k-left-right))):
            if l[t]<0:
                temp-=l[t]
        ans = max(ans, temp)
print(ans)

Solution (Python):
import heapq
from collections import deque
from functools import lru_cache

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

for l in range(0,K + 1):
  for r in range(0,K - l + 1):
    d = K - r - l
    tmp = 0
    have = []
    if l + r > N:
      continue
    for i in range(0,l):
      tmp += V[i]
      have.append(V[i])
    for j in range(N - r,N):
      tmp += V[j]
      have.append(V[j])
    h = len(have)
    
    have = sorted(have)
    for k in range(0,d):
      
      if k >= h:
        break
      if have[k] > 0:
        break
      tmp -= have[k]
    ans = max(tmp,ans)
    
print(ans)

Solution (Python):
from collections import deque

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

m = min(k, n)
res = 0
for A in range(0, m + 1):
    for B in range(0, m + 1):
        if A + B > m:
            continue
        if B == 0:
            L = v[:A]
        else:
            L = v[:A] + v[-B:]
        L.sort()
        L = deque(L)
        num = k - (A + B)
        for i in range(num):
            if len(L) == 0:
                continue
            elif len(L) == 1:
                if L[0] < 0:
                    L.pop()
            else:
                Remove = L.popleft()
                if Remove > 0:
                    L.appendleft(Remove)
        res = max(res, sum(L))

print(res)

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):
        if l + r > N: continue
        d = K - l - r
        now = 0
        having = []
        for i in range(l):
            now += V[i]
            having.append(V[i])
        for i in range(N-r, N):
            now += V[i]
            having.append(V[i])

        having.sort()
        
        for i in range(d):
            if i >= len(having): break
            if having[i] >= 0: break
            now -= having[i]
        ans = max(ans, now)

print(ans)

Solution (Python):
import heapq
N, K = map(int, input().split())
d = [int(x) for x in map(int, input().split())]
e = d[::-1]

res = 0
num = min(N, K)
for i in range(num + 1):
    for j in range(num - i, -1, -1):
        s = d[:i] + e[:j]
        if not s:
            continue
        heapq.heapify(s)
        res = max(res, sum(s))
        l = min(i + j, K - (i + j))
        while l:
            heapq.heappop(s)
            res = max(res, sum(s))
            l -= 1
print(res)

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

res = 0
num = min(k, n)
for i in range(num + 1):
    for j in range(num + 1 - i):
        l = min(k - (i + j), i + j)
        s = d[:i] + d[-j:] if j != 0 else d[:i]
        heapify(s)
        for _ in range(l):
            tmp = heappop(s)
            if tmp > 0:
                heappush(s, tmp)
        res = max(res, sum(s))
print(res)

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

res = 0
num = min(k, n)
for a in range(num + 1):
    for b in range(num + 1 - a):
        l = min(k - (a + b), a + b)
        s = d[:a] + d[-b:] if b != 0 else d[:a]
        heapify(s)
        for _ in range(l):
            tmp = heappop(s)
            if tmp > 0:
                heappush(s, tmp)
                break
        res = max(res, sum(s))
print(res)