CodeEff/ECCO huggingface dataset:
# Original solution
from collections import deque
from copy import deepcopy
import heapq

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

ans = 0
for i in range(k+1):
    if True:
        for nl in range(i+1):
            nr = min(k - nl, n-nl)
            ansl, ansr = 0, 0
            for n_trash in range(nl):
                ansll, ansrr = 0, 0
                hands = sorted(v[:nl-n_trash])
                for vv in hands:
                    if vv < 0 and n_trash > 0:
                        n_trash -= 1
                    else:
                        ansll += vv
                ansl = max(ansl, ansll)

            for n_trash in range(nr):
                ansrr = 0
                hands = sorted(v[-(nr-n_trash):])
                # print(hands, nr, n_trash)
                for vv in hands:
                    if vv < 0 and n_trash > 0:
                        n_trash -= 1
                    else:
                        ansrr += vv
                ansr = max(ansr, ansrr)
            # print(ansl, ansr)
            ans = max(ans, ansl + ansr)
    else:
        n_trash = n-i
        ans_cur = 0
        for vv in v_sorted:
            if vv < 0 and n_trash > 0:
                n_trash -= 1
            else:
                ans_cur += vv
        ans = max(ans, ans_cur)

print(ans)


# Optimized solution
from collections import deque
from copy import deepcopy
import heapq

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

ans = 0
for i in range(k+1):
    for nl in range(i+1):
        nr = min(k - nl, n-nl)
        ansl, ansr = 0, 0
        for n_trash in range(nl):
            ansll, ansrr = 0, 0
            hands = sorted(v[:nl-n_trash])
            for vv in hands:
                if vv < 0 and n_trash > 0:
                    n_trash -= 1
                else:
                    ansll += vv
            ansl = max(ansl, ansll)

        for n_trash in range(nr):
            ansrr = 0
            hands = sorted(v[-(nr-n_trash):])
            # print(hands, nr, n_trash)
            for vv in hands:
                if vv < 0 and n_trash > 0:
                    n_trash -= 1
                else:
                    ansrr += vv
            ansr = max(ansr, ansrr)
        # print(ansl, ansr)
        ans = max(ans, ansl + ansr)

print(ans)
# Original solution
from collections import deque
from copy import deepcopy
import heapq

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

ans = 0
for i in range(k+1):
    for nl in range(i+1):
        nr = min(k - nl, n-nl)
        ansl, ansr = 0, 0
        for n_trash in range(nl):
            ansll, ansrr = 0, 0
            hands = sorted(v[:nl-n_trash])
            for vv in hands:
                if vv < 0 and n_trash > 0:
                    n_trash -= 1
                else:
                    ansll += vv
            ansl = max(ansl, ansll)

        for n_trash in range(nr):
            ansrr = 0
            hands = sorted(v[-(nr-n_trash):])
            # print(hands, nr, n_trash)
            for vv in hands:
                if vv < 0 and n_trash > 0:
                    n_trash -= 1
                else:
                    ansrr += vv
            ansr = max(ansr, ansrr)
        # print(ansl, ansr)
        ans = max(ans, ansl + ansr)

print(ans)


# Optimized solution
n, k = list(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)
# Original solution
from collections import deque

N, K = [int(s) for s in input().split()]
V = [int(s) for s in input().split()]

que = deque([(0, [], V, 0, True, True)])  # total, negative items, deque, count, left_flag, right_flag
best = 0
while que:
    t, s, v, n, lf, rf = que.pop()
    if n >= K:
        best = max([best, t + sum(s)])
        continue
    if v:
        if lf:
            if v[0] >= 0:
                best = max([best, t + v[0] + sum(s)])
                que.append((t + v[0], s, v[1:], n + 1, lf, rf))
            else:
                que.append((t, s + [v[0]], v[1:], n + 1, lf, rf))
        if rf and len(v) > 1:
            if v[-1] >= 0:
                best = max([best, t + v[-1] + sum(s)])
                que.append((t + v[-1], s, v[:-1], n + 1, lf, rf))
            else:
                que.append((t, s + [v[-1]], v[:-1], n + 1, lf, rf))
    if s:
        s.sort()
        que.append((t, s[1:], [s[0]] + v, n + 1, False, rf))
        que.append((t, s[1:], v + [s[0]], n + 1, lf, False))
        best = max([best, t + sum(s[1:])])

print(best)

# Optimized solution
from collections import deque

N, K = [int(s) for s in input().split()]
V = [int(s) for s in input().split()]

best = 0
for a in range(min([K, N]) + 1):
    for b in range(min([K, N]) - a + 1):
        L = V[:a] + V[N - b:]
        Lp = [i for i in L if i >= 0]
        Lm = [i for i in L if i < 0]
        Lm.sort()
        s = sum(Lp + Lm[min([len(Lm), K - a - b]):])
        best = max([best, s])

print(best)
# Original solution
import sys

n, k, *v = list(map(int, sys.stdin.read().split()))

def main():
    m = min(n, k)
    res = 0
    for i in range(m+1):
        for j in range((m-i)+1):
            l = v[:i]
            r = v[-j:] if j > 0 else []
            take = l + r
            s = sum(take)
            neg = [t for t in take if t < 0]
            neg.sort()
            s -= sum(neg[:(k-(i+j))])
            res = max(res, s)
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

# Optimized solution
import sys

n, k, *v = list(map(int, sys.stdin.read().split()))

def main():
    m = min(n, k)
    ls = [None] * (m + 1)
    rs = [None] * (m + 1)
    l_neg = [None] * (m + 1)
    r_neg = [None] * (m + 1)
    
    ls[0] = 0
    rs[0] = 0
    l_neg[0] = []
    r_neg[0] = []

    for i in range(m):
        l = v[i]; r = v[-(i+1)]
        ls[i+1] = ls[i] + l
        rs[i+1] = rs[i] + r
        
        l_neg[i+1] = l_neg[i].copy()
        if l < 0:
            l_neg[i+1].append(l)
        r_neg[i+1] = r_neg[i].copy()
        if r < 0:
            r_neg[i+1].append(r)
    
    res = 0
    for i in range(m+1):
        for j in range((m-i)+1):
            s = ls[i] + rs[j]
            neg = sorted(l_neg[i] + r_neg[j])
            s -= sum(neg[:k-(i+j)])
            res = max(res, s)
    return res
        
if __name__ == '__main__':
    ans = main()
    print(ans)
# Original solution
from heapq import heappop, heappush

N, K = list(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, K) - left + 1):
        heap = []
        for v in V[:left]:
            heappush(heap, v)

        for v in V[N - right:]:
            heappush(heap, v)

        cnt = left + right

        v = 0
        while cnt < K and len(heap) > 0:
            v = heappop(heap)

            if v >= 0:
                heappush(heap, v)
                break
            cnt += 1

        ans = max(ans, sum(heap))
print(ans)


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

maxi = 0
for i in range(min(N, K)):
    for o in range(i+2):
        hand = []
        for p in range(o):
            hand.append(V[p])
        for p in range(N-(i-o)-1, N):
            hand.append(V[p])
        hand.sort()
        for j in range(K-i-1):
            if len(hand) > 0:
                if hand[0] < 0:
                    del hand[0]
                else:
                    break
        ts = 0
        for k in hand:
            ts += k
        if ts > maxi:
            maxi = ts
print(maxi)
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N,K,*V = list(map(int,read().split())) #*Vで行単位の配列を得られる。
#print(V)

vals = [] #valuesの略。

for L in range(N+1): #左
    for R in range(N+1): #右
        if L+R > N: #このbreakで、うまく左右からとれる。
            break
        get = V[:L] + V[N-R:]
        rest = K - (L+R) #ridの代わりにrest。汎用性がある。
        if rest < 0:
            break
        get.sort(reverse=True) #逆順にしてpop()で抜き出している。
        for _ in range(min(len(get),rest)): #indexを用いないforループは_で。徹底。
            if get[-1] < 0:
                get.pop()
            else:
                break
        vals.append(sum(get)) #最小値を求める際はmax(answer, buffer)ではない。一度配列。

answer = max(vals)
print(answer)

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

answer = 0
for i in range(min(N + 1, K + 1)):
  for j in range(i + 1):
    left = j
    right = i - j
    
    q = []
    for k in range(left):
      q.append(V[k])
    for k in range(N - right, N):
      q.append(V[k])
    q.sort()
    
    tmp = sum(q)
    for k in range(min(K - i, len(q))):
      if q[k] < 0:
        tmp -= q[k]
      else:
        break
    answer = max(answer, tmp)
    
print(answer)
# Original solution
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
opt = ['pol', 'por', 'pul', 'pur']
res = []
def helper(res, Q, M, K):
  if K==0:
    res.append(sum(M))
  else:
    if len(Q) > 0:
      # pol
      helper(res, Q[1:], M+[Q[0]], K-1)
      # por
      helper(res, Q[:-1], M+[Q[-1]], K-1)
      if len(M)>0:
        if min(M) < 0:
          # pul
          helper(res, [min(M)]+Q, [i for i in M if i != min(M)], K-1)
          # por
          helper(res, Q+[min(M)], [i for i in M if i != min(M)], K-1)
    helper(res, Q, M, K-1)
helper(res, V, [], K)
print((max(res)))
      

# Optimized solution
a,k=list(map(int,input().split()))
L=list(map(int,input().split()))
ans=0
 
for i in range(min(k,a)+1):
  for j in range(min(k,a)-i+1):
    S=[0]+L[:i]+L[a-j:]
    S.sort()
    x=0
    while x < k-(j+i):
      if S[x]>=0:
        break
      x+=1
    ans=max(ans,sum(S)-sum(S[:x]))
    
print(ans)
# Original solution
def main():
    N, K = (int(i) for i in input().split())
    V = [int(i) for i in input().split()]
    if 2*N <= K:
        ans = sum(v for v in V if v > 0)
        return print(ans)
    ans = 0
    R = min(N, K)
    for a in range(R+1):
        for b in range(R+1):
            if R < a+b:
                continue
            can_de = K - a - b
            cur_e = V[:a] + V[:-(b+1):-1]
            cur_e.sort(reverse=True)
            while cur_e and cur_e[-1] < 0 and 0 < can_de:
                cur_e.pop()
                can_de -= 1
            ans = max(ans, sum(cur_e))

    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N, K = (int(i) for i in input().split())
    V = [int(i) for i in input().split()]
    if 2*N <= K:
        ans = sum(v for v in V if v > 0)
        return print(ans)
    ans = 0
    for a in range(N+1):
        for b in range(N+1):
            if N < a+b:
                continue
            if K < a+b:
                continue
            rest = K - a - b
            cur_e = V[:a]
            if b > 0:
                cur_e += V[-b:]
            cur_e.sort(reverse=True)
            while cur_e and cur_e[-1] < 0 and 0 < rest:
                cur_e.pop()
                rest -= 1
            ans = max(ans, sum(cur_e))

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
import heapq
import copy

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

M = min(N, K)

ans = 0
a = 0
ah = []
for i in range(M + 1):
    if i > 0:
        v = V[i - 1]
        a += v
        if v < 0:
            heapq.heappush(ah, v)

    b = a
    bh = copy.copy(ah)
    for j in range(M + 1):
        if (i + j) > M:
            break
        if j > 0:
            v = V[N - j]
            b += v
            if v < 0:
                heapq.heappush(bh, v)

        c = b
        ch = copy.copy(bh)
        for n in range(min(K - i - j, len(ch))):
            c += -heapq.heappop(ch)
        if c > ans:
            ans = c

print(ans)

# Optimized solution
import heapq
import copy

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

M = min(N, K)

ans = 0
for i in range(M + 1):
    for j in range(M - i + 1):
        l = V[:i] + V[N - 1:N - j - 1:-1]
        t = sum(l)
        l.sort()
        for n in range(min(K - i - j, len(l))):
            if l[n] >= 0:
                break
            t -= l[n]
        if t > ans:
            ans = t

print(ans)
# Original solution
N,K = list(map(int, input().split()))
V = list(map(int, input().split()))
from collections import deque
d=deque(V)
my_gem = []
max_value=-1000000000
def nxt(num,cur_v):
        global max_value
        global my_gem
        if num == K :
                return

        if len(d) > 0:

                # sousa A
                gem_v = d.popleft()
                cur_v+=gem_v
                if max_value < cur_v:
                        max_value = cur_v

                my_gem.append(gem_v)
                nxt(num+1,cur_v)

                my_gem.remove(gem_v)
                cur_v -= gem_v
                d.appendleft(gem_v)

                # sousa B
                gem_v = d.pop()
                cur_v+=gem_v
                if max_value < cur_v:
                        max_value = cur_v

                my_gem.append(gem_v)
                nxt(num+1,cur_v)
                my_gem.remove(gem_v)

                cur_v -= gem_v
                d.append(gem_v)

        # sousa C
        itr = 0
        for pushgem in my_gem:
                itr+=1
                my_gem.remove(pushgem)
                cur_v -= pushgem

                if max_value < cur_v:
                        max_value = cur_v

                d.appendleft(pushgem)
                nxt(num+1,cur_v)
                d.popleft()

                cur_v += pushgem
                my_gem.append(pushgem)
                if itr == len(my_gem):
                        break

        # sousa D
        itr = 0
        for pushgem in my_gem:
                my_gem.remove(pushgem)
                cur_v -= pushgem

                if max_value < cur_v:
                        max_value = cur_v

                d.append(pushgem)
                nxt(num+1,cur_v)
                d.pop()

                cur_v += pushgem
                my_gem.append(pushgem)
                if itr == len(my_gem):
                        break

nxt(0,0)
print(max_value)

# Optimized solution
N,K = list(map(int, input().split()))
V = list(map(int, input().split()))
import sys
max_value=-1000000000

for i in range(K+1):
        for left in range(i+1):
                right= i - left

                leftlist = V[:left]

                if right == 0:
                        rightlist = []
                else:
                        rightlist = V[-right:]

        #       print(left)
        #       print(right)


                leftlist.extend(rightlist)

                leftlist.sort()


#               for push in range(K-i):

                num = 0
                for value in range(len(leftlist)):
                        num+=1
                        if num > K-i:
                                break

                        if leftlist[value] > 0:
                                break
                        leftlist[value]=0
        #       print(leftlist)



                s = sum(leftlist)
                if max_value < s:
                        max_value = s

                if left+right > N:
                        print(max_value)
                        sys.exit()

print(max_value)
# Original solution
import copy
import bisect
from collections import deque

def dfs(i, k, v, x):
    if i >= k:
        return sum(x)
    y = [0, 0, 0, 0]
    if len(v) > 0:
        p = v.popleft()
        xi = copy.copy(x)
        bisect.insort(xi, p)
        y[0] = dfs(i + 1, k, v, xi)
        v.appendleft(p)
    if len(v) > 1:
        p = v.pop()
        xi = copy.copy(x)
        bisect.insort(xi, p)
        y[1] = dfs(i + 1, k, v, xi)
        v.append(p)
    if len(x) > 0:
        p = x[0]
        xi = copy.copy(x)
        del xi[0]
        v.appendleft(p)
        y[2] = dfs(i + 1, k, v, xi)
        _ = v.popleft()
        v.append(p)
        y[3] = dfs(i + 1, k, v, xi)
        _ = v.pop()
    return max(y)

n, k = list(map(int, input().split()))
v = deque(list(map(int, input().split())))
x = []
ans = dfs(0, k, v, [])
print(ans)


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

ans = 0
if n == 1:
    ans = max(0, v[0])
else:
    ans = 0 if k < n else sum(v)
    for i in range(min(k + 1, n)):
        for j in range(i + 1):
            t = v[:j]
            if j != i:
                t += v[j - i:]
            t.sort()
            for p in range(k - i):
                if len(t) > 0 and t[0] < 0:
                    t.pop(0)
                else:
                    break
            if len(t) == 0:
                t = [0]
            ans = max(ans, sum(t))
print(ans)
# Original solution
from heapq import*
n,k=list(map(int,input().split()))
*v,=list(map(int,input().split()))
motimono=[]
ans=[]
if k>=n:
    k-=n
    heapify(v)
    ans.append(sum(v))
    for i in range(k):
        if len(v)>0:
            heappop(v)
        ans.append(sum(v))
    print((max(ans)))
else:
    v*=2
    for j in range(1,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)))

# Optimized solution
n,k=list(map(int,input().split()))
*v,=list(map(int,input().split()))
motimono=[]
ans=[]
if k>=n:
    k-=n
    ans.append(sum(v))
    v.sort()
    for i in range(min(k,len(v))):
        v[i]=0
        ans.append(sum(v))
    print((max(ans)))
else:
    v*=2
    for j in range(1,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,len(motimono))):
                motimono[i]=0
                ans.append(sum(motimono))
    print((max(ans)))
# Original solution
from heapq import*
n,k=list(map(int,input().split()))
*v,=list(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)))

# Optimized solution
n,k,*v=list(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)))
# Original solution
n,k,*v=list(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)))

# Optimized solution
n,k,*v=list(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)))
# Original solution
from collections import deque

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

ans = 0
for t in range(k//2 + 1):
    hand = deque(V[:k-t])
    rest = deque(V[k-t:])
    cur_sum = sum(hand)

    for j in range(k-t+1):
        put_back = 0
        rev_hand = sorted(hand)

        for i in range(t):
            jewel = rev_hand[i]
            if jewel < 0:
                put_back -= jewel
            else:
                break

        candidate = cur_sum + put_back
        ans = max(candidate, ans)

        to_rest = hand.pop()
        rest.appendleft(to_rest)
        to_hand = rest.pop()
        hand.appendleft(to_hand)

        cur_sum += to_hand - to_rest

print(ans)

# Optimized solution
n, k = list(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)))
# Original solution
N , K = list(map(int,input().split()))
D = list(map(int,input().split()))

maxValue = 0
actList = [0]*K

for i in range(4**K):
    act = i
    valList = []
    V = D.copy()

    for j in range(K):
        actList[j] = (act % 4)
        act = int(act / 4)

    for j in actList:
        if(j == 0): # 操作 A
            if(len(V) == 0):
                continue
            valList.append(V.pop(0))
        elif(j == 1): # B
            if(len(V) == 0):
                continue
            valList.append(V.pop())
        elif(j == 2): # C
            if(len(valList) == 0):
                continue
            V.insert(0,valList.pop(0))
        elif(j == 3): # D
            if(len(valList) == 0):
                continue
            V.append(valList.pop(0))
        valList.sort()

    val = sum(valList)
    if maxValue < val:
        maxValue = val

print(maxValue)



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

maxValue = 0

for i in range(min(N,K)+1):
    for j in range(min(N,K)-i+1):
        left = D[:i]
        right = D[N-j:]
        merge = (left + right + [0])
        merge.sort()

        index = 0

        for k in range(K-i-j):
            if (merge[index] < 0):
                index += 1
            else:
                break

        val = sum(merge[index:])
        if(maxValue < val):
            maxValue = val

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

ans = 0
for left in range(K + 1):
    for right in range(K + 1):
        if left > N - right or left + right > K:
            continue

        G = V[:left] + V[N - right:]
        G.sort()
        dis = 0
        for i, g in enumerate(G):
            if i >= K - (left + right) or g >= 0:
                break
            dis += g

        ans = max(ans, sum(G) - dis)

print(ans)

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

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

        diff = K - left - right
        takes = V[:left] + V[N - right:]
        takes.sort(reverse=True)

        while diff > 0 and takes and takes[-1] < 0:
            takes.pop()
            diff -= 1

        ans = max(ans, sum(takes))

print(ans)