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-----
6 4
-10 8 2 1 2 6

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
n, k = map(int, input().split())
v = list(map(int, input().split()))
reverse_v = v[::-1]
lst = [0] * (k + 1)
left = [[]]
right = [[]]
for i in range(1, n+1):
  left.append(v[:i])
  right.append(reverse_v[:i])

for cnt in range(1, k+1):
  rest = k - cnt
  total = 0
  if cnt <= n:
    for j in range(cnt+1):
      lst_j = left[j] + right[cnt-j]
      lst_j.sort()
      l = cnt
      for idx in range(cnt):
        if lst_j[idx] >= 0:
          l = idx
          break
      if l == cnt:
        value = 0
      else:
        flg = min(l, rest)
        value = sum(lst_j[flg:])
      if value > total:
        total = value
    lst[cnt] = total

ans = max(lst)
print(ans)

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)


n, k = list(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)


import heapq
import itertools
def main():
    n,k=list(map(int, input().split()))
    v=[int(i) for i in input().split()]
    #k回Vの両端から取り出したり詰めたりして持ってるものの価値の最大化をする
    v_1 = v[::-1]
    #左から取る回数をA、右から取る回数をBとしたとき、価値が負の宝石を捨てる操作は（k-(A+B)）回できる
    #これを利用して全探索
    res = 0
    for i in range(k+1):
        j = 0
        while(i+j<=min(n,k)):

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

    print(res)
def __starting_point():
    main()

__starting_point()

def abc128_d():
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
    ans = 0

    for a in range(max(1, k+1)):  # 左から取る個数
        for b in range(max(1, k-a+1)):  # 右から取る個数
            if a+b > n: break
            arr = []
            if a > 0: arr += v[:a]
            if b > 0 and a < n: arr += v[max(a, 0, n-b):]
            arr.sort()
            for j in range(max(1, a+b)):  # 戻す個数
                if a+b+j > k: break
                score = sum(arr[j:])
                ans = max(ans, score)
                #print(a, b, j, score, arr)
    print(ans)

def __starting_point():
    abc128_d()
__starting_point()

# 左から取り出すパターンは最大50通り
# 右から取り出すパターンは最大50通り
# その組み合わせは2500通り
# その全通りに対して、マイナスの石を引けるだけ引くパターンを試すと50
# 125000
# すべて試す

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
V = [0] + list(map(int,readline().split())) + [0]
N += 2
K += 2

leftsum = 0
leftminus = []
ans = -(10 ** 9)
for left in range(min(N,K)):
  leftsum += V[left]
  if V[left] < 0:
    leftminus += [V[left]]
  rightsum = 0
  rightminus = []
  limit = min(N - (left + 1) , K - (left + 1))
  for right in range(N - 1, N - limit - 1, -1):
    rightsum += V[right]
    if V[right] < 0:
      rightminus += [V[right]]
    allsum = leftsum + rightsum
    rest = max(K - ((left + 1) + (N - right)),0)
    allminus = sorted(leftminus + rightminus)
    allsum -= sum(allminus[:rest])
    if allsum > ans:
      ans = allsum
print(ans)

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

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


n,k=map(int,input().split())
v=[int(x) for x in input().split()]

r=min(n,k)
ans=-10**9
for i in range(r+1):
  for j in range(r+1):
    if i+j > r: continue;
    l=v[:i]+v[::-1][:j]
    m=sorted([l[x] for x in range(len(l)) if l[x]<0])[:k-(i+j)]
    ans=max(ans, sum(l)-sum(m))
    
print(ans)

from heapq import heapify, heappop, heappush

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

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

ans = 0

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

print(ans)

from heapq import *
n, k = list(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)


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")

#i: 左から取る回数
for i in range(targ+1):
    #j: 右を取る回数
    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)

#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

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

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

    # 方針: 操作Aの回数・操作Bの回数で全探索
    ans = 0
    R = min(N,K)

    for i in range(R+1):
        for j in range(R+1-i):
            tmp = 0
            q = []# 価値が負の宝石をいれる(C)
            
            for k in range(i):
                tmp += V[k]
                if V[k] < 0:
                    q.append(V[k])
            for k in range(j):
                tmp += V[N-1-k]
                if V[N-1-k] < 0:
                    q.append(V[N-1-k])

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

def __starting_point():
    main()

__starting_point()

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

def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

ans = 0  # 何もしないと0なので、ansの初期値は0


# pick->取り出す操作をする回数(listより多く取り出さないように注意)
for pick in range(min(K+1, N+1)):
    # 右から取り出す数
    for right in range(pick+1):
        left = pick-right  # 左から取り出す数
        pick_list = V[:right]+V[N-left:]

        # queueに戻す操作
        pick_list = sorted(pick_list)
        tmp_ans = sum(pick_list)  # 戻す前の合計値
        rem = min(K-pick, len(pick_list))  # 戻す操作をできる回数
        for i in range(rem):  # 負の値のものをできるだけ戻す
            if pick_list[i] < 0:
                tmp_ans -= pick_list[i]
            else:
                break
        ans = max(tmp_ans, ans)
print(ans)

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

ans = -10**9
for back in range(n+1):
    for left in range(min(k-back+1, n+1)):
        for right in range(min(k-back-left+1, n-left+1)):
            hand = []
            hand.extend(v[:left])
            if right>0:
                hand.extend(v[-right:])
            hand.sort()
            ans = max(ans, sum(hand[back:]))

print(ans)

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

#左からl個、右からr個取り出す
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()
        #d回まで持っている宝石(価値がマイナス)を戻す
        for i in range(d):
            if i >= len(having): break
            if having[i] >= 0: break
            now -= having[i]
        ans = max(ans, now)

print(ans)


import heapq
N, K = list(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)


from heapq import *
n, k = list(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):
        trash = k - (a + b)
        s = d[:a] + d[-b:] if b != 0 else d[:a]
        heapify(s)
        for _ in range(min(trash, a + b)):
            tmp = heappop(s)
            if tmp > 0:
                heappush(s, tmp)
                break
        res = max(res, sum(s))
print(res)


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

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

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

# equeue

from collections import deque
import heapq


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    res = 0
    for pull in range(K+1):
        push = K - pull
        if push < 0 or push > N:
            continue
        for left_push in range(push+1):
            tmp_que = deque(V)
            tmp_heap = []
            heapq.heapify(tmp_heap)
            right_push = push - left_push
            for _ in range(left_push):
                heapq.heappush(tmp_heap, tmp_que.popleft())
            for _ in range(right_push):
                heapq.heappush(tmp_heap, tmp_que.pop())

            tmp_res = sum(tmp_que)
            for i in range(min(push, pull)):
                x = heapq.heappop(tmp_heap)
                if x >= 0:
                    heapq.heappush(tmp_heap,x)
                    break


            res = max(res, sum(tmp_heap))
    print(res)
    return


def __starting_point():
    main()
__starting_point()

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
V = LIST()

ans = 0
tmp_sum = 0

for i in range(1, min(K, N)+1):
	left = K-i
	for j in range(i+1):
		tmp = V[:j] + V[N-(i-j):]
		tmp.sort()
		idx = bisect_left(tmp, 0)
		ans = max(ans, sum(tmp) - sum(tmp[:min(idx, left)]))

print(ans)


n, k = 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)

N,K=list(map(int,input().split()))
V=list(map(int,input().split()))
r=min(N,K)
ans=0
for a in range(r+1):
    for b in range(r-a+1):
        tmp,minus=0,[]
        for i in range(a):
            t=V[i]
            tmp+=t
            if t<0:
                minus.append(t)
        for j in range(b):
            t=V[N-1-j]
            tmp+=t
            if t<0:
                minus.append(t)
        tmp-=sum(sorted(minus)[:K-(a+b)])
        ans=max(ans,tmp)
print(ans)


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)

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-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)


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

ans = -1

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

import math
from collections import deque
n,k=map(int,input().split())
v=list(map(int,input().split()))
#k回までだったー誤読
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()
        #取った個数より多く詰めようとしないように！
        #残りk-i回ある
        for j in range(i,min(k,2*i)):#それ以上詰められない場合
            #0より小さい場合は書き換える
            if s[j-i]<0:s[j-i]=0
        #取り出したやつの最大(戻す場合は0)
        ans=max(ans,sum(s))
        #残りk-j回ある(breakの時のjはやってないので)
        #ここからはいい感じに出すのと入れるのを繰り返す(偶数の場合はこのままか)
        #必要すらない、k回を使い切らなくていいので
        #print(sum(s))
print(ans)

# 初期入力
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)

#取る個数take_num、返す個数reverse(t +r <=K)個全て決める

ans =[]
take_V =[] #最後に持っている宝石の価値
#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) #返す数はtake_numではなく、Kから引く
        for lef in range(tak+1):
            for rev in range(reverse +1):
            
                take =[]                    #取った宝石
                rig =N-(tak -lef )          #lef:左側の取る数 rig:右側の取る数
                take.extend(V[    :lef])
                take.extend(V[rig:   ])
                take.sort()
                take_V.append(sum(take[rev:]))
        
    ans =max(take_V)
print(ans)

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)


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)

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

for i in range(1, K + 1):#i個以下取り出し、K - i個以下戻す＃１００
  nownow = 0
  for p in range(i + 1):#[0:i] から [N - i:N]まで取り出さないところを選べる#100
    #[p:p + N - i]を取り出さない
    if i < N:
      now = sorted(V[:p] + V[p + N - i:])
    else:
      now = V
    #print(now, i, p)
    index = bisect.bisect_right(now, 0)
    #index個の負の数がある。
    if K - i >= index:
      nownow = sum(now[index:])
    else:
      nownow = sum(now[K - i:])
    ans = max(ans, nownow)
    #print(now, nownow, ans)

print(ans)      


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)


n, k = map(int, input().split())
v = list(map(int, input().split()))
vv = [0] * (n + 1)
for i in range(n):
    vv[i + 1] = vv[i] + v[i]
sumv = vv[n]
ans = 0
for l in range(n):
    for r in range(l - 1, n):
        c = r - l + 1
        if n - c > k:
            continue
        x = []
        value = sumv - (vv[r + 1] - vv[l])
        for i in range(n):
            if not l <= i <= r:
                x.append(v[i])
        x.sort()
        for i in range(max(0, min(k - (n - c), len(x)))):
            if x[i] < 0:
                value -= x[i]
            else:
                break
        ans = max(value, ans)
print(ans)

n, k = list(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)


N, K = map(int, input().split())
V = list(map(int, input().split()))
W = V[::-1]
R = min(N, K)
ans = -float('inf')
for left in range(R+1):
    for right in range(R+1):
        if left+right > R: continue
        A = V[:left]+W[:right]
        tmp = sum(A)
        
        rest = K - left - right
        A = [k for k in A if k < 0]
        A.sort()
        if rest >= 0:
            tmp -= sum(A[:min(rest, len(A))])
        ans = max(tmp, ans)

print(ans)

# 初期入力
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)

#取る個数take_num、返す個数reverse(t +r <=K)個全て決める

ans =[]
take_V =[] #最後に持っている宝石の価値
#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):
            #for rev in range(reverse +1):
            
                take =[]  #取った宝石
                rig =N-(tak -lef )          #lef:左側の取る数 rig:右側の取る数
                take.extend(V[    :lef])
                take.extend(V[rig:   ])
                take.sort()
                reverse =min(K -tak,tak) #返す数はtake_numではなく、Kから引く
                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)

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)


from heapq import *
n, k = list(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)


n,k=map(int,input().split())
v=list(map(int, input().split()))
m=min(n,k)
ans=0
for i in range(m+1): #A
  for j in range(m+1-i): #B
    l=[]
    l=l+v[0:i]+v[n-j:n]
    l.sort()
    for kk in range(min(k-i-j, i+j)):
      if l[kk]<0:
        l[kk]=0
    ans=max(ans, sum(l))
print(ans)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc128/tasks/abc128_d

n, k = list(map(int, input().strip().split()))
value = list(map(int, input().strip().split()))
res = 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
        s = []
        for i in range(l):
            now += value[i]
            s.append(value[i])
        for i in range(r):
            now += value[n-i-1]
            s.append(value[n-i-1])
        s.sort()
        for i in range(d):
            if i >= len(s):
                break
            if s[i] > 0:
                break
            now -= s[i]
        res = max(res, now)

print(res)



import bisect

N, K = [int(x) for x in input().split()]
V = [int(x) for x in input().split()]
M = min(N, K)

ans = 0
juwel = []
for l in range(M + 1):
    for r in range(M - l + 1):
        juwel = sorted(V[:l] + V[N - r:])
        s = bisect.bisect_left(juwel, 0)
        s = min(s, K - l - r)
        juwel = juwel[s:]
        ans = max(ans, sum(juwel))

print(ans)

import sys
input = sys.stdin.readline

N,K = (int(x) for x in input().rstrip('\n').split())
vs = [int(x) for x in input().rstrip('\n').split()]
g = [vs[0],vs[-1]]
rest = K
for k in [K-1,K]:
  for b in range(K//2):
    t = k-b
    if t>N:
      t=N
    for i in range(t+1):
      v = []
      if i <t:
        v.extend(vs[:i])
        v.extend(vs[-(t-i):])
        for _ in range(b):
          if min(v)<0:
            v.remove(min(v))
          else:
            break
      else:
        v.extend(vs[:t])
        for _ in range(b):
          if min(v)<0:
          	v.remove(min(v))
      g.append(sum(v))
if max(g)<0:
  print(0)
else:
  print(max(g))

n,k=map(int,input().split())
v=[int(x) for x in input().split()]

r=min(n,k)
ans=-10**9
for i in range(r+1):
  for j in range(r+1):
    if i+j > r: continue;
    l=sorted(v[:i]+v[::-1][:j])
    for a in range(k-(i+j)+1):
      ans=max(ans, sum(l[a:]))
    
print(ans)

N,K=map(int,input().split())
V=list(map(int,input().split()))
import heapq
turn=min(N,K)
m=0
for A in range(turn+1):
  for B in range(turn+1-A):
    h=[]
    heapq.heapify(h)
    if A>0:
      h=V[:A]+h
    if B>0:
      h=h+V[len(V)-B:]
    heapq.heapify(h)  

    ans=sum(h)
    for i in range(K-A-B):
      if h!=[]:
        f=heapq.heappop(h)
 
        if f<0:
          ans-=f
    m=max(ans,m)


    
print(m)   

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

ans = V[0]
for l in range(min(K, N)+1):
    for r in range(min(K, N)-l+1):
        v = V[:l] + V[N-r:]
        rest = K - (l + r)
        v.sort()
        tmp = 0
        for x in v:
            if rest and x < 0:
                rest -= 1
            else:
                tmp += x
        if ans < tmp:
            ans = tmp
print(ans)

n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(min(n, k) + 1):
    for j in range(min(n, k) - i + 1):
        lis = sorted(v[:i] + v[n - j:])
        for l in range(k - i - j + 1):
            ans = max(ans, sum(lis[l:]))
print(ans)

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

ans = 0

for lg in range(K+1):
    for rg in range(K-lg+1):
        if lg+rg > N:
            break
        for ls in range(K-lg-rg+1):
            if ls > lg:
                break
            for rs in range(K-lg-rg-ls+1):
                if rs > rg:
                    break

                lv = V[:lg]
                rv = V[N-rg:]

                """
                print(lg, ls, rg, rs)
                print(lv, rv)
                print(lv[:lg-ls], rv[:rg-rs])
                print()
                """
                lv.sort()
                lv.reverse()
                rv.sort()
                rv.reverse()

                ans = max(sum(lv[:lg-ls])+sum(rv[:rg-rs]), ans)

print(ans)

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

ans = 0
for left in range(n + 1):
    for right in range(n + 1):
        if left == 0 and right == 0:
            continue
        rest = k - left - right
        if left + right > n or rest < 0:
            break
        arr = v[:left] + v[n - right:]
        minus = 0
        neg = [x for x in arr if x < 0]
        if len(neg) > 0:
            neg.sort()
            minus = sum(neg[:rest])
        ans = max(ans, sum(arr) - minus)

print(ans)

from heapq import heappush, heappop
from random import randint
from time import time

class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def __len__(self):
        return len(self.queue)
    def __contains__(self, item):
        return item in self.queue

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

ans = 0

#取得する操作を何回行うか？
for i in range(0,m+1):

	#操作残り回数
	lef = m-i

	hp = PriorityQueue()
	#左側からどれだけ取るか？
	for j in range(0,i+1):
		if j>n :
			break

		#左側からj個取る
		for k in range(0,j):
			hp.push(v[k])

		#右側から i-j個取る
		for k in range(0,i-j):
			if n-1-k < j:
				break
			hp.push(v[n-1-k])

		#minusは戻す
		for k in range(0,lef):
			if len(hp) == 0:
				break
			top = hp.pop()
			if top>=0 :
				hp.push(top)
				break

		ss = 0
		while len(hp)>0:
			ss += hp.pop()

		ans = max(ans,ss)

print(ans)

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

R = min(N,K)
point = 0
max_point = 0
hand = []

for i in range(R+1):
    for a in range(i+1):
        if i==a:
            hand = V[:a]
        else:
            hand = V[:a]+V[-(i-a):]
        negahand = [k for k in hand if k < 0]
        negahand.sort()
        if K-i > len(negahand):
            trash = -sum(negahand)
        else:
            trash = -sum(negahand[:K-i])
        point = sum(hand) + trash
        max_point = max(max_point,point)

print(max_point)

n , k = list(map(int, input().split()))
v = list(map(int,input().split()))
ma = float('INF')*(-1)
m = min(n,k)
for i in range(m+1):
    for j in range(m+1-i):
        vl=v[:i]
        vr=v[n-j:]
        ans = sum(vl)+sum(vr)
        vb=vl+vr
        vb.sort()
        m2 = min(k-i-j, len(vb))
        for l in range(m2):
            if vb[l]<0:
                ans-=vb[l]
            else:
                break
        ma = max(ans,ma)
if ma<0:
    ma = 0
print(ma)


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))

# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
from collections import deque
import heapq


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, Vi):
    ans = 0
    for ab in range(min(N, K) + 1):
        for a in range(ab + 1):
            b = ab - a
            have = Vi[:a] + Vi[N - b:]
            have.sort()
            s = sum(have)
            for i in range(K - ab):
                if len(have) <= i:
                    break
                elif have[i] < 0:
                    s += abs(have[i])
                else:
                    break
            ans = max(ans, s)
    print(ans)


def __starting_point():
    N, K = list(map(int, input().split()))
    Vi = [int(i) for i in input().split()]
    solve(N, K, Vi)

    # # test
    # import random
    # from func import random_str
    # N, K = 100, 50
    # Vi = [random.randint(-(10 ** 7), 10 ** 7) for _ in range(N)]
    # solve(N, K, Vi)

__starting_point()

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

ans = 0

for gets in range(min(N, K)+1):
    for lgets in range(gets+1):
        rgets = gets - lgets
        haves = V[:lgets]+V[(N-rgets):]
        haves.sort()
        removes = K - gets
        for i in range(min(removes, len(haves))):
            if haves[i] < 0:
                haves[i] = 0
            else:
                break
        ans = max(ans, sum(haves))
print(ans)



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 + 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 filter(lambda x: x > 0, a)))
print(ans)

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)


def __starting_point():
    main()

__starting_point()

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)

import heapq
from collections import deque
n , k = map(int,input().split())
v = list(map(int,input().split()))
ans = 0
for i in range(n+1):
    for j in range(n+1):
        if i+j > n or i+j > k:
            continue
        p = v[:]
        d = deque(p)
        a = []
        heapq.heapify(a)
        for t in range(i):
            heapq.heappush(a,d.popleft())
        for l in range(j):
            heapq.heappush(a,d.pop())
        nokori = k-i-j
        for s in range(nokori):
            if a:
                now = heapq.heappop(a)
                if now > 0:
                    heapq.heappush(a,now)
                    break
            else:
                break
        ans = max(ans,sum(a))
print(ans)

N,K=map(int,input().split())
V=list(map(int,input().split()))
r,ans=min(N,K),0
for a in range(r+1):
  for b in range(r-a+1):
    tmp,minus=0,[]
    for i in range(a):
      tmp+=V[i]
      if V[i]<0:
        minus.append(V[i])
    for j in range(b):
      tmp+=V[N-j-1]
      if V[N-j-1]<0:
        minus.append(V[N-j-1])
    tmp-=sum(sorted(minus)[:K-(a+b)])
    ans=max(ans,tmp)
print(ans)

from collections import deque

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

w = deque(v)
ans = 0
for i in range(k+1):
    if i > n:
        break
    s = v[:i]
    for j in range(k+1-i):
        if j > n-i:
            break
        t = sorted(v[n-j:] + s, reverse=True)
        u = sum(t)
        for l in range(k+1-i-j):
            ans = max(ans, u)
            if not t:
                break
            u -= t.pop()
print(ans)

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

ans = 0

for a in range(min(N,K)+1):
    for b in range(min(N,K)-a+1):
        cur = V[:a] + V[N-b:]
        cur.sort()

        idx = 0
        while idx < min(K-a-b, len(cur)):
            if cur[idx] > 0: break
            else: idx += 1
        
        ans = max(ans, sum(cur[idx:]))
    
print(ans)

n, k, *a = list(map(int, open(0).read().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
        b = sorted(a[:l] + a[n - r:])
        c = min(k - l - r, len(b) - 1)
        ans = max(ans, sum(b[c:] if b[c] < 0 else [x for x in b if x > 0]))
print(ans)


N,K = 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):
    G = V[:i]+V[N-j:]
    G.sort()
    for j in range(K-i-j+1):
      ans = max(ans,sum(G[j:]))

print(ans)

N, K = map(int, input().split())
V = list(map(int, input().split()))
result = 0
for a in range(N + 1):
    for b in range(N + 1):
        if a + b > K or a + b > N:
            break
        out = V[:a] + V[N-b:]
        out.sort()
        sum_val = sum(out)
        for i in range(min(a + b, K - a - b)):
            if out[i] >= 0:
                break
            sum_val -= out[i]
        result = max(result, sum_val);
print(result)

import heapq
from collections import deque
from functools import lru_cache

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 - 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)
    #print(have)
    have = sorted(have)
    for k in range(0,d):
      #print(have,sum(have))
      if k >= h:
        break
      if have[k] > 0:
        break
      tmp -= have[k]
    ans = max(tmp,ans)
    
print(ans)


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):
		#print(i, j)
		nl = v[:i] + v[n-j:]
		nl.sort()
		#print(nl)
		tmp = sum(nl)
		for t in range(min(k-(i+j), i+j)):
			tmp = max(tmp, tmp-nl[t])
			#print("行いましたよ!")
		#print(tmp)
		ans = max(tmp, ans)
print(ans)

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


def main():
    n, k = list(map(int, input().split()))
    v = list(map(int, input().split()))
    reversed_v = [0] + v[::-1]
    v = [0] + v
    ans = -float("inf")
    for i in range(n + 1):
        for j in range(n + 1):
            if i + j > min(n, k):
                continue
            now_k = k - i - j
            if now_k < 0:
                continue
            q = []
            for l in range(1, i + 1):
                q.append(v[l])
            for l in range(1, j + 1):
                q.append(reversed_v[l])
            q.sort()
            for l in range(len(q)):
                if q[l] < 0 and now_k > 0:
                    q[l] = 0
                    now_k -= 1
            ans = max(ans, sum(q))
    print(ans)


def __starting_point():
    main()

__starting_point()

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

ans=0
for l in range(N+1):
  for r in range(N+1):
    if l+r>N or l+r>K:break
    arr=V[:l]
    if r:arr+=V[-r:]
    arr.sort()
    rem=K-l-r
    tmp=0
    for a in arr:
      if a<0 and rem:
        rem-=1
      else:
        tmp+=a
    ans=max(ans,tmp)
print(ans)

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

ans = 0
for l in range(N+1):
    for r in range(N+1):
        if l+r > N or l+r > K: break
        arr = V[:l]
        if r: arr += V[-r:]
        arr.sort()
        rem = K - l - r
        tmp = 0
        for a in arr:
            if a < 0 and rem:
                rem -= 1
            else:
                tmp += a
        ans = max(ans, tmp)
print(ans)

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 = list(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


def __starting_point():
    main()

__starting_point()

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

ans = 0

for l in range(n):
    for r in range(n+1)[::-1]:
        if l <= r and 0 <= (l+n-r) <= k: # l+n-r個拾う
            q = v[:l] + v[r:n]
            q.sort(reverse = True)
            
            for i in range(k-(l+n-r)):
                if q == []:
                    break
                if q[-1] < 0:
                    q.pop()
                else:
                    break

            ans = max(ans, sum(q))
        else:
            continue

print(ans)

#import math
#import itertools
#import numpy as np
from collections import deque


INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    d=LIST()
    #q=deque(d)
    nkmin=min(n,k)
    stop=10**9
    ans=0
    for i1 in range(1,1+nkmin):
        for i2 in range(i1+1):
            temp=d[0:i2]+d[n-(i1-i2):]
            #print(temp,i1,i2)
            temp=sorted(temp)
            #print(temp,i1,i2)
            for i3 in range(i1):
                if temp[i3]>=0 or i3>=k-i1:
                    stop=i3
                    break
                stop=10**9
            if stop!=10**9:
                #print(temp[i3:],1)
                ans=max(sum(temp[i3:]),ans)
    
    print(ans)



def __starting_point():
    do()
__starting_point()

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)

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


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


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

            #print(ln, rn, pv, mv)
            ans = max(ans, pv + sum(mv))

    print((max(0, ans)))


def __starting_point():
    solve()

__starting_point()

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

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

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

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

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

def __starting_point():
    n,k,v=readinput()
    ans=main2(n,k,v)
    print(ans)

__starting_point()

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):
        # skip
        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)

from collections import deque
n, k = list(map(int, input().split()))
v = list(map(int, input().split()))
d = deque(v)

t = min(n, k)
score = 0
for a in range(t+1):
    for b in range(t-a+1):
        tmp_d = d.copy()
        jems = []
        for i in range(a):
            jems.append(tmp_d.pop())
        for i in range(b):
            jems.append(tmp_d.popleft())
        jems.sort()
        for i in range(min(len(jems), k-b-a)):
            if jems[i] < 0:
                jems[i] = 0
            else:
                break
        tmp_score = sum(jems)
        if tmp_score > score:
            score = tmp_score
print(score)


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

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

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return list(map(int, input().split()))
def MI1(): return list(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 math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

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
            # print(a, b, k)
            # print(left, right)
            lst = sorted(left + right)
            # print(lst)
            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
                    # print(tmp)
                else:
                    break
            ans = max(ans, sm)
    print(ans)


def __starting_point():
    solve()

__starting_point()

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)))


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

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

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


import math,itertools,fractions,heapq,collections,bisect,sys,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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

  ans=0
  for i in range(k):
    if i+1<n:
      for l in range(i+1):
        r=i-l
  
        _ans=0
        _v=[]
        for x in range(l+1):
          _ans+=v[x]
          _v.append(v[x])
        for x in range(r):
          _ans+=v[n-x-1]
          _v.append(v[n-x-1])

        _v.sort()
        for j in range(min(len(_v),k-i-1)):
          if _v[j]<0:
            _ans-=_v[j]
          else:
            break
        # print(_v,l,r,_ans)
        ans=max(ans,_ans)
    else:
      _v=v.sort()
      _ans=sum(v)
      _k=n-k-1
      for j in range(_k):
        if _v[j]<0:
          _ans-=_v[j]
        else:
          break
      ans=max(ans,_ans)

  return ans

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


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

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


N,K = list(map(int,input().split()))
V = list(map(int,input().split()))
left = [0]*(K+1)
right = [0]*(K+1)

for k in range(1,min(N+1,K+1)):
    max_vk = 0
    for j in range(k//2+1):        
        push = j
        pop = k-j
        #print(k,pop,push)
        if pop>N:
            continue
        else:
            tmp = sum(sorted(V[:pop])[push:])
        max_vk = max(max_vk,tmp)
    left[k] = max_vk

Vrev = V[::-1]

for k in range(1,K+1):
    max_vk = 0
    for j in range(k//2+1):
        push = j
        pop = k-j
        #print(k,pop,push)
        if pop>N:
            continue
        else:
            tmp = sum(sorted(Vrev[:pop])[push:])
        max_vk = max(max_vk,tmp)
    right[k] = max_vk

for i in range(len(right)-1):
    if right[i+1]<right[i]:
        right[i+1]= right[i]
    if left[i+1]<left[i]:
        left[i+1]=left[i]

ans = 0
NK = K
max_ans = 0
for v in V:
    if v>0:
        max_ans += v
    
for i in range(NK+1):
    ans = max(ans,right[i]+left[NK-i])

print((min(max_ans,ans)))


N,K = list(map(int,input().split()))
V = list(map(int,input().split()))
#print(V)
max_v = 0
have_minus = []
for left in range(N):
  for right in range(left,N + 1)[::-1]:
    if len(V[:left]) + len(V[right:]) > K: 
      break
    #print (V[:left], V[right:])
    sum_ = sum(V[:left]) + sum(V[right:])
    have_minus = [num for num in V[:left]+V[right:] if num < 0]
    have_minus.sort()
    #print (f"have_minus={have_minus}" )
    d = max(0,K - (len(V[:left]) + len(V[right:])))
    for i in range(min(d, len(have_minus))):
        sum_ -= have_minus[i]   
    #print (f"sum_ = {sum_}")    
    
    max_v = max(max_v ,sum_)
print(max_v)      
    
    
       


N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for anum in range(min(N, K) + 1):
    owned = V[:anum]
    for bnum in range(min(N, K) - anum + 1):
        if bnum > 0:
            owned.append(V[-bnum])
        owned.sort()
        cdnum = K - (anum + bnum)
        total = 0
        for v in owned:
            if v < 0 and 0 < cdnum:
                cdnum -= 1
            else:
                total += v
        ans = max(ans, total)
print(ans)

N,M=list(map(int,input().split()))
l=list(map(int,input().split()))
S=min(M,N)
ans=0
for i in range(S+1):
   for j in range(S-i+1):
      mem=l[0:i]+l[N-j:]
      for k in range(min((M-i-j),len(mem))):
         if min(mem)<0:
            mem.remove(min(mem))
      ans=max(ans,sum(mem))
print(ans)

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

ans = []
# きっちりK回しなくていいみたい
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)))



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

def main():
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        for j in range(i, n):
            h=[0]
            heapq.heapify(h)
            count = 0
            for p in range(i-1):
                heapq.heappush(h, v[p])
                count += 1
            for m in range(j+1, n):
                heapq.heappush(h, v[m])
                count += 1
            while h[0] < 0 and count < k:
                t = heapq.heappop(h)
                count += 1
            if count <= k:
                ans = max(ans,sum(h))
    counts = n
    heapq.heapify(v)
    while h[0] < 0 and counts < k:
        t = heapq.heappop(v)
        counts += 1
    if counts <= k:
        ans = max(ans,sum(v))
    print(ans)
   
def __starting_point():
    main()
__starting_point()


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
            
            #print(ka, kb, kcd)
            s = V[:ka] + V[-kb:] if kb != 0 else V[:ka]
            s.sort()
            #print(s[kcd:], sum(s[kcd:]))
            MAX = max(MAX, sum(s[kcd:]))

print(MAX)

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

a=list(map(int,input().split()))
a_reverse=list(reversed(a))
b=sorted(a)
s=sum(a)

ans=[]

for i in range(k+1):
  if i>n:
    I=i-n
    for j in range(I): 
      if j<n:
        ans1=s-b[j]
    ans.append(ans1)
  elif i==n:
    ans.append(s)
  elif i==0:
    ans.append(0)
  else:
    for h in range(i+1):
      H=i-h
      c=[]
      for x in range(h):
        c.append(a[x])
      for y in range(H):
        c.append(a_reverse[y])
        
      c.sort()
      S=sum(c)
      for g in range(1,k-i+1):
        if g<=i:
          if c[g-1]<0:
            S-=c[g-1]

      ans.append(S)
      
print(max(ans))

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
    # print (s,t)
    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)

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



def __starting_point():
    main()

__starting_point()

n,k = map(int,input().split())
v = list(map(int,input().split()))
ans = 0
for i in range(min(n+1,k+1)):
    for j in range(min(n+1-i,k+1-i)):
        g = []
        x = 0
        while x < i:
            g.append(v[x])
            x += 1
        y = 0
        z = -1
        while y < j:
            g.append(v[z])
            y += 1
            z -= 1
        g.sort()
        x = k - i - j
        for z in range(min(len(g),x)):
            if g[z] < 0:
                g[z] = 0
            else:
                break
        ans = max(ans,sum(g))
print(ans)