CodeEff/ECCO huggingface dataset:
# Original solution
n, k = list(map(int, input().split()))
vs = list(map(int, input().split()))

from collections import deque
from heapq import heappush, heappop
from itertools import product

res = 0

for comb in product([1, 2, 3, 4], repeat=k):
    dq = deque(vs)
    hq = []
    valid = True
    for i in range(k):
        s = comb[i]
        if s == 1:
            if len(dq) > 0:
                heappush(hq, dq.popleft())
            else:
                valid = False
                break
        elif s == 2:
            if len(dq) > 0:
                heappush(hq, dq.pop())
            else:
                valid = False
                break
        elif s == 3:
            if len(hq) > 0:
                dq.appendleft(heappop(hq))
            else:
                valid = False
                break
        else:
            if len(hq) > 0:
                dq.append(heappop(hq))
            else:
                valid = False
                break
    if valid:
        res = max(res, sum(hq))

print(res)

# Optimized solution
n, k = list(map(int, input().split()))
vs = list(map(int, input().split()))

from collections import deque
from heapq import heappush, heappop

res = 0

for i in range(0, min(k, n) + 1):
    for j in range(i + 1):
        a = j
        b = i - j

        hq = []
        dq = deque(vs)

        for _ in range(a):
            heappush(hq, dq.popleft())
        for _ in range(b):
            heappush(hq, dq.pop())

        c = k - a - b
        for _ in range(c):
            if len(hq) == 0:
                break
            v = heappop(hq)
            if v > 0:
                heappush(hq, v)
                break

        res = max(res, sum(hq))

print(res)
# Original solution
from copy import deepcopy

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

all_score = sum(V)
memo = {}

def dfs(queue, hand, depth):
    # print(queue, hand, depth)
    if depth == K:
        score = all_score - sum(queue)
        memo[queue] = score
        # print('return', queue, score)
        return score
    if queue in memo:# and memo[queue] is not None:
        # print('memo')
        return memo[queue]

    if queue not in memo:
        memo[queue] = None

    max_score = all_score - sum(queue)
    if len(queue) > 0:
        # A
        A_queue = queue[1:]
        if A_queue not in memo:
            A_hand = deepcopy(hand)
            A_hand.append(queue[0])
            score = dfs(A_queue, A_hand, depth + 1)
            if score > max_score:
                max_score = score
        # B
        B_queue = queue[:-1]
        if B_queue not in memo:
            B_hand = deepcopy(hand)
            B_hand.append(queue[-1])
            score = dfs(B_queue, B_hand, depth + 1)
            if score > max_score:
                max_score = score

    for i in range(len(hand)):
        # C
        C_queue = (hand[i],) + queue
        if C_queue not in memo:
            C_hand = deepcopy(hand)
            C_hand = C_hand[:i] + C_hand[i+1:]
            score = dfs(C_queue, C_hand, depth + 1)
            if score > max_score:
                max_score = score

        # D
        D_queue = queue + (hand[i],)
        if D_queue not in memo:
            D_hand = deepcopy(hand)
            D_hand = D_hand[:i] + D_hand[i + 1:]
            score = dfs(D_queue, D_hand, depth + 1)
            if score > max_score:
                max_score = score

    memo[queue] = max_score
    # print(queue, max_score)
    return max_score

ans = dfs(V, [], 0)
print(('0' if ans < 0 else ans))

# Optimized solution
from copy import deepcopy

N, K = list(map(int, input().split()))
V = tuple(map(int, input().split()))
max_score = -1000000000
for i in range(K+1):
    for j in range(K - i + 1):
        if i + j > N:
            continue
        # 左からi個取る
        hand = list(V[:i])
        # 右からj個取る
        hand.extend(V[N-j:])
        # 最大(K - i - j)個戻せる
        # print(i, j, hand)
        score = sum(hand)
        counter = 0
        for h in sorted(hand):
            counter += 1
            if K - i - j - counter < 0:
                break
            if h < 0:
                score -= h
        if max_score < score:
            max_score = score
print(max_score)
# Original solution
import copy

N, K = list(map(int, input().split()))
V = [int(i) for i in input().split()]

value = 0
# k+1個取って，ret-1個戻す
num = min(N*2,K)
for k in reversed(list(range(num))):
    for ret in range(num-k): #戻す個数はret個
        if (ret < k+1):
            #print('{}個取って{}戻す'.format(k+1,ret))
            for i in range(k+1+1): # 左右の分け方
                tmp = []
                V_tmp = copy.copy(V)
                #print('元々：',V_tmp)
                tmp.extend(V_tmp[:i]) # 左端
                #print('左端：',V_tmp[:i])
                V_tmp = V_tmp[i:]
                #print('左端取った：',V_tmp)
                if (k+1-i) > 0:
                    tmp.extend(V_tmp[-(k+1-i):]) #右端
                    #print('右端：',V_tmp[-(k+1-i):])
                # V_tmp = V_tmp[:-(k+1-i)]
                # print('右端取った：',V_tmp)
                if V_tmp == []:
                    break
                # ret個戻す
                tmp = list([x for x in tmp if x not in sorted(tmp)[:ret]])
                #print('手元の宝石：',tmp)
                value = max(value,sum(tmp))
            #print()

print(value)

# Optimized solution
import copy

N, K = list(map(int, input().split()))
V = [int(i) for i in input().split()]

result = 0
# i個取る
for i in range(min(N,K)+1):
    #print('i:',i)
    for sp in range(i+1): # 左右の分け方
        #print('right',sp)
        #print('left',i-sp)
        tmp = []
        V_tmp = copy.copy(V)
        #print('元々：',V_tmp)
        tmp.extend(V_tmp[:sp]) # 左端追加
        #print('left',V_tmp[:sp])
        tmp.extend(V_tmp[N-(i-sp):]) #右端追加
        #print('right',V_tmp[N-(i-sp):])
        #print(tmp)
        tmp = sorted(tmp)
        value = sum(tmp)
        # ret個戻す
        for ret in range(0, min(K-i,i)): #残り操作回数か取った石の個数iの小さい方
            if ret < i:
                # マイナスの価値は戻す
                if tmp[ret] < 0:
                    value -= tmp[ret]
                    #print('捨てた宝石：',tmp[ret])
            else:
                break
        result = max(result,value)
            #print()

print(result)
# Original solution
import heapq
N,K=list(map(int, input().split()))
V=list(map(int, input().split()))

ans=-10**9
for l in range(min(N,K)+1):
    for r in range(max(1,min(N,K)+1-l)):
        for d in range(max(1,K+1-l-r)):
            h=V[:l]
            heapq.heapify(h)
            for i in range(r): heapq.heappush(h, V[-1-i])
            for i in range(min(d,len(h))): heapq.heappop(h)
            ans=max(ans,sum(h))
print(ans)

# Optimized solution
import heapq
N,K=list(map(int, input().split()))
V=list(map(int, input().split()))

ans=-10**9
for l in range(min(N,K)+1):
    for r in range(max(1,min(N,K)+1-l)):
        for d in range(max(1,min(N,K-l-r)+1)):
            h=V[:l]
            heapq.heapify(h)
            for i in range(r): heapq.heappush(h, V[-1-i])
            for i in range(min(d,len(h))): heapq.heappop(h)
            ans=max(ans,sum(h))
print(ans)
# Original solution
import bisect

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

ans = 0

if N < K :
    pp = K
    K = N
else :
    pp = K
for a in range(1,K+1) :
    for i in range(a+1) :
        G = []
        G.extend(V[:i])
        G.extend(V[len(V)-(a-i):])
        G.append(0)
        G = sorted(G)
        #bi = bisect.bisect(G,0)
        #G = G[min(bi-1,K-a):]

        cnt = 0
        calc = 0
        for i in range(len(G)) :
            if G[i] < 0 :
                if cnt < pp-a :
                    cnt += 1
                else :
                    calc += G[i]
            else :
                calc += G[i]


        ans = max(ans,calc)

print(ans)


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

ans = 0

P = min(N,K)

for a in range(1,P+1) :
    for i in range(a+1) :
        cnt = 0
        calc = 0
        GET = V[:i] + V[N-(a-i):]
        GET = sorted(GET)
        
        for g in GET :
            if (g < 0) and (cnt < K-a) :
                cnt += 1
            else :
                calc += g
        
        ans = max(ans, calc)
print(ans)
# Original solution
from heapq import heappop, heapify


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

# i: 操作回数
# j: 取り出す個数
# k: 左から取り出す範囲 [0, k)
ans = 0
for i in range(K + 1):
    for j in range(min(N + 1, i + 1)):
        for k in range(j + 1):
            right = N - j + k
            tmp = V[:k] + V[right:]

            put_out_cnt = i - j
            heapify(tmp)
            while tmp and put_out_cnt > 0:
                heappop(tmp)
                put_out_cnt -= 1
            ans = max(ans, sum(tmp))
print(ans)


# Optimized solution
N, K, *V = list(map(int, open(0).read().split()))

# i: 操作回数
# j: 取り出す個数
# k: 左から取り出す範囲 [0, k)
ans = 0
for i in range(K + 1):
    for j in range(min(N + 1, i + 1)):
        for k in range(j + 1):
            right = N - j + k
            tmp = V[:k] + V[right:]
            tmp.sort()
            ans = max(ans, sum(tmp) - sum([t for t in tmp if t < 0][: i - j]))
print(ans)
# Original solution
import copy

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

INF = 10 ** 8


def rec(rest_ope, now_d, now_hand):

    if rest_ope == 0:
        return sum(now_hand)

    max_price = -INF

    if len(now_d) > 0:
        left_d = copy.copy(now_d)
        left_hand = copy.copy(now_hand)
        left_hand.append(left_d.pop(0))

        max_price = max(max_price, rec(rest_ope - 1, left_d, left_hand))

        right_d = copy.copy(now_d)
        right_hand = copy.copy(now_hand)
        right_hand.append(right_d.pop(-1))

        max_price = max(max_price, rec(rest_ope - 1, right_d, right_hand))

    if len(now_hand) > 0:
        drop_hand = copy.copy(now_hand)
        drop_hand.pop(drop_hand.index(min(drop_hand)))  # 最小値を削除

        max_price = max(max_price, rec(rest_ope - 1, now_d, drop_hand))

    # do nothing
    max_price = max(max_price, rec(rest_ope - 1, now_d, now_hand))

    return max_price


print((rec(K, V, [])))


# Optimized solution
import copy

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

INF = 10 ** 8


# mode 0: can pop left, pop right, drop
#      1: can pop right, drop
#      2: can drop
#      3: can not do anything
def rec(rest_ope, now_d, now_hand, mode):

    if rest_ope == 0:
        return sum(now_hand)

    max_price = -INF

    if len(now_d) > 0:
        if mode == 0:
            left_d = copy.copy(now_d)
            left_hand = copy.copy(now_hand)
            left_hand.append(left_d.pop(0))

            max_price = max(max_price, rec(rest_ope - 1, left_d, left_hand, 0))

        if mode <= 1:
            right_d = copy.copy(now_d)
            right_hand = copy.copy(now_hand)
            right_hand.append(right_d.pop(-1))

            max_price = max(max_price, rec(rest_ope - 1, right_d, right_hand, 1))

    if len(now_hand) > 0:
        if mode <= 2:
            drop_hand = copy.copy(now_hand)
            drop_hand.pop(drop_hand.index(min(drop_hand)))  # 最小値を削除

            max_price = max(max_price, rec(rest_ope - 1, now_d, drop_hand, 2))

    # do nothing
    max_price = max(max_price, rec(rest_ope - 1, now_d, now_hand, 3))

    return max_price


print((rec(K, V, [], 0)))
# Original solution
def sousa(k,hand,v):
    if k==0:
        # print(k,sum(hand),hand,v)
        ans.append(sum(hand))
        return
    if len(v)>0:
        # 左から取る
        sousa(k-1,hand+[v[0]],v[1:])
        # 右から取る
        sousa(k-1,hand+[v[-1]],v[:-1])

    if len(hand)>0:
        # 右に入れる
        hand.sort()
        array=[hand[0]]
        sousa(k-1,hand[1:],v+array)
        # 左に入れる
        sousa(k-1,hand[1:],array+v)



n,k=list(map(int,input().split()))
v=list(map(int,input().split()))
ans=[0]
sousa(k,[],v)
# print(ans)
print((max(ans)))


# Optimized solution
n,k=list(map(int,input().split()))
v=list(map(int,input().split()))
ans=[]
for lhs in range(k+1):
    for rhs in range(k-lhs+1):
        if lhs+rhs<=n:
            array=v[:lhs]+v[n-rhs:]
        else:
            array=v[:]
        # print(v[:lhs],v[n-rhs:])
        for i in range(k+1-lhs-rhs):
            array.sort()
            ans.append(sum(array[i:]))
# print(ans)
print((max(ans)))
# Original solution
import sys

input = sys.stdin.readline


def main():
    N, K = list(map(int, input().split()))
    V = list(map(int, input().split()))
    _V = V[::-1]

    ans = 0
    for k in range(K + 1):
        n_pop = min(k, N)
        n_push = K - n_pop
        for i in range(n_pop + 1):
            l, r = i, n_pop - i
            L = V[:l] + _V[:r]
            L.sort()
            for j in range(min(n_pop, n_push)):
                if L[j] < 0:
                    L[j] = 0
                else:
                    break
            v = sum(L)
            if v > ans:
                ans = v

    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys

input = sys.stdin.readline


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

    ans = -float("inf")
    for t in range(min(N, K) + 1):
        s = K - t
        for l in range(t + 1):
            r = t - l
            gem = V[:l]
            gem += V[-r:] if r != 0 else []
            gem.sort()
            value = sum(gem)
            for i in range(min(s, t)):
                if gem[i] < 0:
                    value -= gem[i]
                else:
                    break
            ans = max(ans, value)

    print(ans)


if __name__ == "__main__":
    main()
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

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

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

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

  ans=-inf
  a=min(n,k)
  for i in range(a+1):
    sm=0
    for j in range(a+1-i):
      if j!=0:
        _q=l[:i]+l[-j:]
      else:
        _q=l[:i]

      q=[]
      for x in _q:
        heapq.heappush(q,x)
      ans=max(ans,sum(q))

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

  return ans

# main()
print((main()))


# Optimized solution
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

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

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

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

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

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

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

  return ans

# main()
print((main()))
# Original solution
import itertools
n,k=list(map(int,input().split()))
d=list(map(int,input().split()))
oll=list(itertools.product(['a','b','c','d'],repeat=k))
ans=0
for ol in oll:
    tv=0
    t=[]
    td=d[:]
    for o in ol:
        if o=='a':
            t+=[td.pop(0)]
            tv=sum(t)
            ans=max(ans,tv)
        elif o=='b':
            t+=[td.pop(-1)]
            tv=sum(t)
            ans=max(ans,tv)
        elif o=='c':
            if len(t)!=0:
                td.insert(0,min(t))
                t.remove(min(t))
                tv=sum(t)
                ans=max(ans,tv)
            else:
                break
        elif o=='d':
            if len(t)!=0:
                td.append(min(t))
                t.remove(min(t))
                tv=sum(t)
                ans=max(ans,tv)
            else:
                break
print(ans)

# Optimized solution
n,k=list(map(int,input().split()))
d=list(map(int,input().split()))
ans=0
for l in range(min(n,k)+1):
    for r in range(min(n-l,k-l)+1):
        tl=d[:l]+d[-r:] if r>0 else d[:l]
        tk=k-l-r
        s=0
        for t in sorted(tl):
            if t<0 and tk>0:
                s+=-t
                tk-=1
            ans=max(ans,sum(tl)+s)
print(ans)
# Original solution
from collections import deque
import copy
dp = {}

def dfs(N, K, k, have, q):
  if k == K:
    return sum(have)
  else:
    if not ((k, tuple(q)) in dp):
      a = [sum(have)]
      if len(q) > 0:
        tmp_q = copy.copy(q)
        tmp_have = copy.copy(have)
        v = tmp_q.popleft()
        tmp_have.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
        tmp_q = copy.copy(q)
        tmp_have = copy.copy(have)
        v = tmp_q.pop()
        tmp_have.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
      if len(have) > 0:
        tmp_q = copy.copy(q)
        tmp_have = sorted(copy.copy(have))
        v = tmp_have.pop(0)
        tmp_q.appendleft(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
        tmp_q = copy.copy(q)
        tmp_have = sorted(copy.copy(have))
        v = tmp_have.pop(0)
        tmp_q.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
      dp[(k, tuple(q))] = max(a)
    return dp[(k, tuple(q))]


N, K = list(map(int, input().split()))
V = deque(list(map(int, input().split())))
print((dfs(N, K, 0, [], V)))




# Optimized solution
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
M = min(N, K)
ans = 0
for p in range(M+1):
  for q in range(M-p+1):
    left = []
    right = []
    if p > 0:
      left = V[:p]
    if q > 0:
      right = V[-q:]
    have = sorted((left+right).copy())
    if len(have) > 0:
      for i in range(min(len(have),K-p-q+1)):
        if have[i] > 0:
          break
      ans = max(sum(have[i:]),ans)
print(ans)
# Original solution
def main():
    import collections
    import copy
    N,K = list(map(int, input().split()))
    V = collections.deque(list(map(int, input().split())))

    answer = [[0]*(K+1) for _ in range(K+1)]


    for i in range(1,K+1):
        for j in range(1,min(i+1,N+1)):
            opt = 0
            for k in range(j+1):
                tmp = copy.deepcopy(V)
                tmp2 = collections.deque()
                for _ in range(k):
                    tmp2.append(tmp.popleft())
                for _ in range(j-k):
                    tmp2.append(tmp.pop())
                tmp2 = list(tmp2)
                tmp2.sort()
                for l in range(min(i-j,j)):
                    if tmp2[l] < 0:
                        tmp2[l] = 0
                S = sum(tmp2)
                if S > opt:
                    opt = S
            answer[i][j] = opt
    print((max(max(answer))))

main()

# Optimized solution
def main():
    import collections
    import copy
    N,K = list(map(int, input().split()))
    V = collections.deque(list(map(int, input().split())))

    answer = [[0]*(K+1) for _ in range(K+1)]


    for i in range(1,K+1):
        for j in range(max(1,i//2),min(i+1,N+1)):
            opt = 0
            for k in range(j+1):
                tmp = copy.deepcopy(V)
                tmp2 = collections.deque()
                for _ in range(k):
                    tmp2.append(tmp.popleft())
                for _ in range(j-k):
                    tmp2.append(tmp.pop())
                tmp2 = list(tmp2)
                tmp2.sort()
                for l in range(min(i-j,j)):
                    if tmp2[l] < 0:
                        tmp2[l] = 0
                S = sum(tmp2)
                if S > opt:
                    opt = S
            answer[i][j] = opt
    Ans = 0
    for i in range(K+1):
        for j in range(K+1):
            if answer[i][j] > Ans:
                Ans = answer[i][j]
    print(Ans)

main()
# Original solution
from itertools import product
from collections import deque

def state_brute_force(state, count):
    state_list = [state for _ in range(count)]
    for s in product(*state_list):
        yield s


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

ans = 0

pop_l = deque.popleft
pop_r = deque.pop
add_l = deque.appendleft
add_r = deque.append

stop_condition = sum([item for item in D if item > 0])
if stop_condition > 0:
    for cmb in state_brute_force([pop_l, pop_r, add_l, add_r], K):
        q = deque(D)
        now = []
        value = 0
        for operation in cmb:
            if operation == add_l or operation == add_r:
                if len(now) == 0:
                    break
                item = min(now)
                now.remove(item)
                operation(q, item)
            if operation == pop_l or operation == pop_r:
                if len(q) == 0:
                    break
                now.append(operation(q))
        value = max(value, sum(now))
        ans = max(ans, value)
        if ans == stop_condition:
            break

print(ans)




# Optimized solution
N, K = list(map(int, input().split()))
D = list(map(int, input().split()))

ans = 0

for left in range(K + 1):
    for right in range(K - left + 1):
        if left + right > N:
            break
        items = list(D[0:left])
        items.extend(D[::-1][0:right])
        dis = K - (left + right)
        i = 0
        items = sorted(items, reverse=True)
        while True:
            ans = max(ans, sum(items))
            if i < dis and len(items) > 0:
                i += 1
                items.pop()
                continue
            else:
                break

print(ans)
# Original solution
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    N, K = list(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()

# Optimized solution
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    N, K = list(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()