CodeEff/ECCO huggingface dataset:
# Original solution
import heapq
import copy

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


def dfs(q, have, count, operate):
    if operate == 0:
        heapq.heappush(have, q[0])
        q = q[1:]
    elif operate == 1:
        heapq.heappush(have, q[-1])
        q = q[:-1]
    elif operate == 2:
        sub = heapq.heappop(have)
        q.insert(0, sub)
    elif operate == 3:
        sub = heapq.heappop(have)
        q.append(sub)

    count += 1
    if count >= k:
        return sum(have)

    a = -float('inf')
    b = -float('inf')
    c = -float('inf')
    d = -float('inf')
    e = dfs(q, have, count, -1)  # 何もしない

    if len(q) > 0:
        a = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 0)
        b = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 1)
    if len(have) > 0:
        c = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 2)
        d = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 3)

    return max(a, b, c, d, e)


print((dfs(v, [], -1, -1)))


# Optimized solution
n, k = list(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):
        li = v[:a]
        if b > 0:
            li += v[-b:]
        li.sort()
        count = 0
        while (a + b + count < k):
            if len(li) > 0 and li[0] < 0:
                count += 1
                li = li[1:]
            else:
                break
        ans = max(ans, sum(li))

print(ans)
# Original solution
# -*- coding:utf-8 -*-
import copy

def solve():
    N, K = list(map(int, input().split()))
    V = list(map(int, input().split()))
    
    ans = 0
    M = min(N,K)
    for l in range(M+1):
        having = []
        for r in range(M+1):
            if l+r > M: break
            if l+r == 0: continue
            # 左からl, 右からr個の宝石を取り出す
            having = V[:l] + V[::-1][:r]
            having.sort(reverse=True)

            restK = K - (l+r)

            for _ in range(restK):
                if len(having)!=0 and having[-1] < 0:
                    having.pop()
                    continue
                break

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

if __name__ == "__main__":
    solve()


# Optimized solution
# -*- coding:utf-8 -*-

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

    """方針
    Dequeueから宝石をとる。最後に好きなだけ宝石を戻す。
    dp[i][j] := 左からi個、右からj個取ったときの最大値
    """
    dp = [[0 for _ in range(K+1)] for __ in range(K+1)]
    dp[0][0] = 0  # dpを使ってなくて草

    ans = -float("inf")
    for i in range(0, K+1):
        for j in range(0, K+1):
            if i+j > K: break
            if i+j > N: break
            if i==0 and j==0:
                ans = 0
                continue

            hasVs = Vs[0:i] + Vs[N-j:N]
            hasVs.sort(reverse=True)

            restK = K - (i+j)
            while restK > 0:
                restK -= 1
                if hasVs == []:
                    break
                if hasVs[-1] < 0:
                    hasVs.pop(-1)
                    continue
                break

            ans = max(ans, sum(hasVs))

    print(ans)



if __name__ == "__main__":
    solve()
# Original solution
# -*- coding:utf-8 -*-
import sys
import heapq


def solve():
    N, K = list(map(int, sys.stdin.readline().split()))
    Vs = list(map(int, sys.stdin.readline().split()))

    ans = 0
    for i in range(0, K+1):
        for j in range(0, K+1):
            if i+j > K: break
            if i+j > N: break
            #
            if i==0 and i==j:
                continue

            _Vs = Vs[::-1]
            have = Vs[0:i]+_Vs[0:j]
            have.sort(reverse=True)

            M = i+j
            while M < K:
                if len(have) == 0: break
                if have[-1] < 0:
                    have.remove(have[-1])
                    M += 1
                    continue
                break

            ans = max(ans, sum(have))

    print(ans)



if __name__ == "__main__":
    solve()


# Optimized solution
# -*- coding:utf-8 -*-
import sys
import heapq


def solve():
    N, K = list(map(int, sys.stdin.readline().split()))
    Vs = list(map(int, sys.stdin.readline().split()))

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

            _Vs = Vs[::-1]
            have = Vs[0:i]+_Vs[0:j]
            have.sort(reverse=True)

            M = i+j
            while M < K:
                if len(have) == 0: break
                if have[-1] < 0:
                    have.remove(have[-1])
                    M += 1
                    continue
                break

            ans = max(ans, sum(have))

    print(ans)



if __name__ == "__main__":
    solve()
# Original solution
from itertools import accumulate
N, K = list(map(int, input().split()))
*V, = list(map(int, input().split()))

ans = 0
for a in range(N+1):
    for b in range(N+1):
        if a+b>N:continue
        
        if a and b:
            qa, qb = list(accumulate([0]+sorted(V[:a]))), list(accumulate([0]+sorted(V[-b:])))
            sa, sb = sum(V[:a]), sum(V[-b:])
            for c in range(a+1):
                for d in range(b+1):
                    if a+b+c+d<=K:
                        ans = max(ans, sa+sb-qa[c]-qb[d])
        elif a:
            qa = list(accumulate([0]+sorted(V[:a])))
            sa = sum(V[:a])
            for c in range(a+1):
                if a+c<=K:
                    ans = max(ans, sa-qa[c])
        elif b:
            qb = list(accumulate([0]+sorted(V[-b:])))
            sb = sum(V[-b:])
            for d in range(b+1):
                if b+d<=K:
                    ans = max(ans, sb-qb[d])

print(ans)

# Optimized solution
from itertools import accumulate
N, K = list(map(int, input().split()))
*V, = list(map(int, input().split()))

ans = 0
for a in range(N+1):
    for b in range(N+1):
        if a+b>N:continue
        t = []
        if a:
            t += V[:a]
        if b:
            t += V[-b:]
        t.sort()
        t = [0]+t
        
        v = sum(t)
        for c in range(a+b+1):
            v -= t[c]
            if a+b+c<=K:
                ans = max(ans, v)

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

score = {}

def Compute(n, D, S):
    D2 = tuple(D)
    S2 = tuple(S)
    if (n, D2, S2) in score:
        return score[(n, D2, S2)]
    if n == 0:
        return sum(S)

    candidate = [Compute(n - 1, D, S)]
    if len(D) > 0:
        candidate.append(Compute(n - 1, D[1:], sorted(S + [D[0]])))
        candidate.append(Compute(n - 1, D[:-1], sorted(S + [D[-1]])))
    for i in range(len(S)):
        candidate.append(Compute(n - 1, D + [S[i]], S[:i] + S[i+1:]))
        candidate.append(Compute(n - 1, [S[i]] + D, S[:i] + S[i+1:]))
    return max(candidate)

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


# Optimized solution
import bisect

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

score = -1e100

M = min(N, K)
for A in range(0, M + 1):
    for B in range(0, M - A + 1):
        S = []
        if A > 0:
            S += V[:A]
        if B > 0:
            S += V[-B:]
        S.sort()
        score = max(score, sum(S) - sum([x for x in S if x < 0][:max(0, K - A - B)]))

print(score)
# Original solution
n,k,*v=list(map(int,open(0).read().split()))
m=0
r=range
for i in r(n+1):
 for j in r(min(k,n)-i+1):
  t=sorted(v[:i]+v[-j:]*(j>0))
  while t and(k-i-j)*t[0]<0:t.pop(0);j+=1
  m=max(m,sum(t))
print(m)

# Optimized solution
n,k,*v=list(map(int,open(0).read().split()))
m=0
r=range
for i in r(n+1):
 for j in r(min(k,n)-i+1):
  t=sorted(v[:i]+v[::-1][:j])
  while t and(k-i-j)*t[0]<0:t.pop(0);j+=1
  m=max(m,sum(t))
print(m)
# Original solution
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))

import heapq
ans = 0
for a in range(min(N,K)+1):
    for b in range(min(N,K)-a+1):
        A = V[:a] + V[N-b:]
        heapq.heapify(A)
        for c in range(min(a+b, K-a-b)):
            small = heapq.heappop(A)
            if small > 0:
                heapq.heappush(A,small)
                break
        ans = max(ans, sum(A))
print(ans)


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

ans = 0
for l in range(N):
  for r in range(N-l+1):
    arr = V[:l] + ([] if r==0 else V[-r:])
    k = len(arr)
    if k > K: continue
    score = sum(arr)
    arr.sort()
    i = 0
    while k < K and i < len(arr):
      if arr[i] >= 0: break
      score -= arr[i]
      k += 1
      i += 1
    ans = max(ans, score)
print(ans)

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

ans = 0
for l in range(N):
    if l > K: break
    for r in range(N-l+1):
        if l+r > K: break
        vs = V[:l] + (V[-r:] if r>0 else [])
        vs.sort()
        k = K-l-r
        t = 0
        for v in vs:
            if v < 0 and k > 0:
                k -= 1
                continue
            t += v
        ans = max(ans,t)
print(ans)
# Original solution
def main():
    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:
                continue
            tmp = []
            for i in range(min(N, left)):
                tmp.append(V[i])

            for j in range(max(left,N-right),N,1):
                tmp.append(V[j])

            nokori = K - left - right
            tmp.sort()
            tmp_sum = sum(tmp)
            for k in range(min(nokori, len(tmp))):
                if tmp[k] < 0:
                    tmp_sum -= tmp[k]

            ans = max(ans, tmp_sum)

    print(ans)





if __name__ == "__main__":
    main()

# Optimized solution
def main():
    N, K = list(map(int, input().split()))
    V = list(map(int, input().split()))
    ans = 0
    for i in range(K+1):
        cand = []
        for left in range(i+1):
            cand = V[:left]
            right = i - left
            cand += V[max(left,N-right):N]

            cnt = K - i
            n = len(cand)
            tmp = sum(cand)
            cand.sort()
            for c in range(min(cnt,n)):
                if cand[c] < 0:
                    tmp -= cand[c]
                else:
                    break
            ans = max(ans, tmp)


    print(ans)




        

if __name__ == "__main__":
    main()
# Original solution
# -*- coding: utf-8 -*-
"""



"""
import sys


from collections import deque
from functools import lru_cache

@lru_cache(maxsize=None)
def dig_left(n, q):
    res = [0]
    for di in range(1, min(n, len(q))+1):
        bu = n - di
        dig = list(q[:di])
        dig.sort()
        while bu and dig and dig[0] < 0:
            dig.pop(0)
            bu -= 1
        res.append(sum(dig))
    return max(res)


@lru_cache(maxsize=None)
def dig_right(n, q):
    res = [0]
    for di in range(1, min(n, len(q))+1):
        bu = n - di
        dig = list(q[-di:])
        dig.sort()
        while bu and dig and dig[0] < 0:
            dig.pop(0)
            bu -= 1
        res.append(sum(dig))
    return max(res)


def solve(N, K, V):
    ans = [0]
    limit = sum([v for v in V if v > 0])
    for left in range(K+1):
        q = deque(V)
        right = K - left
        l_dig = dig_left(left, tuple(V))
        r_dig = dig_right(right, tuple(V))
        ans.append(min(limit, l_dig+r_dig))
    return max(ans)


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


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


# Optimized solution
# -*- coding: utf-8 -*-
"""
D - equeue
https://atcoder.jp/contests/abc128/tasks/abc128_d

"""
import sys


def dig_lr(n, q, lr='L'):
    # 左(もしくは右)側から最大でn回操作した時の結果の最大値を求める
    res = [0]
    for di in range(1, min(n, len(q))+1): #  diは最大で掘る回数
        bu = n - di             #  埋める方に使用する操作回数
        dig = list(q[:di]) if lr == 'L' else list(q[-di:])
        dig.sort()
        while bu and dig and dig[0] < 0: #  マイナスのアイテムが手元にあればマイナスが大きい方から埋める
            dig.pop(0)
            bu -= 1
        res.append(sum(dig))
    return max(res)


def solve(N, K, V):
    ans = [0]
    limit = sum([v for v in V if v > 0]) #  価値がプラスのアイテムだけ取り出せたときの合計(理論上ベストな結果)
    # K操作回の操作を左右で(左:0 右:K), (左:1 右:K-1), ...,  (左:K 右:0),のように割り振っていき、
    # 左・右からゲットできる値の合計値を計算する
    for left in range(K+1):
        right = K - left
        l_dig = dig_lr(left, V, 'L')
        r_dig = dig_lr(right, V, 'R')
        ans.append(min(limit, l_dig+r_dig))
    return max(ans)


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


if __name__ == '__main__':
    main(sys.argv[1:])
# Original solution
#python3
from collections import deque
from heapq import heappop, heappush
def main():
    n, k = list(map(int, input().split()))
    vs = [int(i) for i in input().split()]
    ans = 0
    for l in range(k+1):
        for r in range(k-l+1):
            dl = k-l-r
            q = deque(vs)
            hav = []
            for _ in range(l):
                if len(q) == 0:
                    continue
                v = q.popleft()
                heappush(hav, v)
            for _ in range(r):
                if len(q) == 0:
                    continue
                u = q.pop()
                heappush(hav, u)
            for i in range(dl):
                if len(hav) == 0:
                    break
                val = heappop(hav)
                if val > 0:
                    heappush(hav, val)
            ans = max(ans, sum(hav))
    print(ans)
main()

# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heapify, heappop, heappush 
def main():
    N, K = list(map(int, readline().split()))
    V = [int(i) for i in readline().split()]
    A = V[::-1]
    ans = 0
    for l in range(K+1):
        for r in range(K+1-l):
            if l+r>N:
                continue
            rest = K-(l+r)
            hp = V[:l] + A[:r]
            heapify(hp)
            for _ in range(rest):
                if len(hp)==0:
                    break
                v = heappop(hp)
                if v > 0:
                    heappush(hp, v)
            ans = max(ans, sum(hp))
    print(ans)
if __name__ == '__main__':
    main()
# Original solution
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))

s = 0
for i in range(min(K, N)+1):
    res = K - i
    for j in range(i+1):
        k = i - j

        Q = sorted(V[:j] + V[N-k:])
        minus = sum([q < 0 for q in Q])
        score = sum(Q[min(minus, res):])
        s = max(s, score)

print(s)


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

m=[]
for i in range(k+1):
 for j in range(min(k,n)-i+1):
  # print(i,j)
  t=sorted(v[:i]+v[:~j:-1])
  while t and(k-i-j)*t[0]<0:t.pop(0);j+=1
  m+=sum(t),
print((max(m)))


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

m=[]
for i in range(k+1):
 for j in range(min(k,n)-i+1):
  # print(i,j)
  t=sorted(v[:i]+v[:~j:-1])

  while t and(k-i-j)*t[0]<0:t.pop(0);j+=1
  m.append(sum(t))
print((max(m)))
# Original solution
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))
import heapq 
m = min(N,K)
M = 0
for i in range(m+1):
    for j in range(m-i+1):
        v1 = V[:i]
        v3 = V[N-j:]
        # print(v1,v3)
        v = v1+v3
        heapq.heapify(v)
        h = K - len(v)
        while v and len(v) and h >0:
            q = heapq.heappop(v)
            h-=1
            if q > 0:
                heapq.heappush(v,q)
                break
        tmp = sum(v)
        # print(v,v3)
        M = max(M,tmp)
print(M)

# Optimized solution
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))
import heapq 
m = min(N,K)
M = 0
for i in range(m+1):
    for j in range(m-i+1):
        v1 = V[:i]
        v3 = V[N-j:]
        v = v1+v3
        heapq.heapify(v)
        h = K - len(v)
        while v  and h >0:
            q = heapq.heappop(v)
            h-=1
            if q > 0:
                heapq.heappush(v,q)
                break
        tmp = sum(v)
        # print(v,v3)
        M = max(M,tmp)
print(M)
# Original solution
import heapq 
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
m = min(N,K) #KがNより大きい場合を防ぐ
M = 0 
for i in range(m+1):
    for j in range(m-i+1):
        A1 = A[:i] #前から取る
        A3 = A[N-j:] #後ろから取る
        new_A = A1+A3
        new_A.sort(reverse=True)
        h = K - len(new_A)
        while h >0 and new_A:
            if new_A[-1] > 0:
                break
            else:
                new_A.pop()
                h-=1
        M = max(M,sum(new_A))
print(M)

# Optimized solution
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
m = min(N,K)
M = 0 
for i in range(m+1):
    for j in range(m-i+1):
        v=A[:i]+A[N-j:]
        v.sort()
        v=v[::-1]
        h=K-len(v)
        while h >0 and v:
            if v[-1] > 0:
                break
            else:
                v.pop()
                h-=1
        M=max(M,sum(v))
print(M)
# Original solution
from bisect import bisect_left
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))

act = min(N, K)

ans = - 10 ** 19
for i in range(act + 1):
  for a in range(i + 1):
    for b in range(i - a + 1):
      itm = []
      itm += V[:a]
      itm += V[N-b:]
      itm.sort()
      idx = bisect_left(itm, 0)
      prize = sum(itm[min(idx, K - a - b):])
      ans = max(ans, prize)
print(ans)

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

ans = - 10 ** 19
# i: Dから取り出す宝石の個数
for i in range(min(k + 1, n + 1)):
  # j: 左からとる個数(i-jが右からとる個数)
  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)
# Original solution
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
U = V[::-1]
ret = 0

m = min(N, K)
for l in range(m+1):
    for r in range(m+1-l):
        hold = V[:l] + U[:r]
        hold.sort()
        for d in range(K+1-l-r):
            ret = max(ret, sum(hold[d:]))

print(ret)

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

m = min(N, K)
for l in range(m+1):
    for r in range(m+1-l):
        hold = V[:l] + V[N-r:]
        hold.sort()
        for d in range(K+1-l-r):
            ret = max(ret, sum(hold[d:]))

print(ret)
# Original solution
n, k = list(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 + 1 - l):
        if l + r > n:
            continue
        suteru = k - l - r
        get = []
        for i in range(l):
            get.append(v[i])
        for i in range(n - 1, n - 1 - r, -1):
            get.append(v[i])
        get.sort()
        minus = 0
        while minus < min(suteru, len(get)) and get[minus] < 0:
            minus += 1
        ans = max(ans, sum(get[minus:]))
print(ans)


# Optimized solution
n, k = list(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 + 1 - l):
        if l == r == 0 or l + r > n:
            continue
        a = sorted(v[:l] + v[n - r:])
        m = min(k - l - r, len(a) - 1)
        ans = max(ans, sum(a[m:] if a[m] <
                           0 else [x for x in a if x > 0]))
print(ans)
# Original solution
n, k = list(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):
    bag = []
    bag += v[:a]
    bag += v[len(v)-b:]
    bag.sort()
    if len(bag) > 0:
      for c in range(k-a-b):
        if bag[0] < 0:
          bag.pop(0)
        if len(bag) == 0:
          break
    ans = max(ans, sum(bag))
      
print(ans)

# Optimized solution
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
ans = 0
for i in range(K+1):
  for j in range(N, max(N-1-(K-i), i-1), -1):
    bag = []
    bag += V[:i] + V[j:]
    bag.sort()
    idx = 0
    if len(bag) == 0:
      continue
    if len(bag) == 1:
      ans = max(ans, sum(bag))
      continue
    if len(bag) == K:
      ans = max(ans, sum(bag))
      continue
    tmp = 0
    for k in range(min(K-len(bag), len(bag))):
      if bag[k] < 0:
        tmp -= bag[k]
    ans = max(ans, sum(bag)+tmp)
print(ans)
# Original solution
import heapq
N, K = [int(_) for _ in input().split()]
V = [int(_) for _ in input().split()]
ans = 0
for il in range(min([N + 1, K + 1])):
    for ir in range(min([N + 1 - il, K + 1 - il])):
        for dl in range(il + 1):
            for dr in range(ir + 1):
                if il + ir + dl + dr > K:
                    continue
                HL = V[:il]
                HR = V[N - ir:N]
                heapq.heapify(HL)
                heapq.heapify(HR)
                value = 0
                for _ in range(dl):
                    v = heapq.heappop(HL)
                    if v >= 0:
                        value += v
                        break
                value += sum(HL)
                for _ in range(dr):
                    v = heapq.heappop(HR)
                    if v >= 0:
                        value += v
                        break
                value += sum(HR)
                ans = max([ans, value])
print(ans)


# Optimized solution
import heapq
N, K = [int(_) for _ in input().split()]
V = [int(_) for _ in input().split()]
ans = 0
for il in range(K + 1):
    for ir in range(K + 1 - il):
        if il + ir > min([N, K]):
            continue
        H = V[:il] + V[N - ir:N]
        heapq.heapify(H)
        now = 0
        for d in range(1, il + ir):
            if il + ir + d > K:
                break
            v = heapq.heappop(H)
            if v >= 0:
                now += v
                break
        now += sum(H)
        ans = max([ans, now])
print(ans)