AtCoder Beginner Contest 128 - equeue

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: MEDIUM

Starter code:

Solutions:
(n, k) = map(int, input().split())
v = [int(i) for i in input().split()]
r = min(n, k)
ans = 0
for a in range(r + 1):
	for b in range(r - a + 1):
		if b >= 1:
			q = v[:a] + v[-b:]
		else:
			q = v[:a]
		t = k - a - b
		m = 0
		for i in sorted(q):
			if i < 0 and t > 0:
				m += abs(i)
				t -= 1
		ans = max(ans, m + sum(q))
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for nab in range(1, min(N + 1, K + 1)):
	nr = K - nab
	for na in range(nab + 1):
		nb = nab - na
		vt = sorted(V[:na] + V[N - nb:])
		for ncd in range(min(nr + 1, nab + 1)):
			np = sum(vt[ncd:])
			ans = max(ans, np)
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
R = min(N, K)
l = []
ans = 0
for a in range(R + 1):
	for b in range(R + 1 - a):
		l = V[:a] + V[N - b:]
		l.sort()
		for i in range(K - a - b + 1):
			ans = max(ans, sum(l[i:]))
print(max(ans, 0))


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
V_r = list(reversed(V))
ans = 0
for take in range(min(N + 1, K + 1)):
	for left in range(take + 1):
		right = take - left
		jewel = V[:left] + V_r[:right]
		rest = K - take
		jewel.sort()
		tmp = sum(jewel)
		for i in range(min(take, rest)):
			if jewel[i] < 0:
				tmp -= jewel[i]
		ans = max(ans, tmp)
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = []
for i in range(1, min(K, N) + 1):
	for a in range(i + 1):
		b = i - a
		AB = V[:a]
		if b > 0:
			AB += V[-b:]
		AB.sort(reverse=True)
		for j in range(K - i):
			if AB and AB[-1] < 0:
				AB.pop()
		ans.append(sum(AB))
print(max(ans))


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
answer = 0
for i in range(min(N, K) + 1):
	for j in range(min(N, K) + 1 - i):
		tempV = V[0:i] + V[N - j:] + [0]
		tempV.sort()
		for k in range(K - i - j):
			if tempV[0] < 0:
				tempV.pop(0)
		if sum(tempV) > answer:
			answer = sum(tempV)
print(answer)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
max_loop = min(k, n)
for left in range(max_loop + 1):
	for right in range(max_loop - left + 1):
		tmp = v[:left] + v[n - right:]
		m = sorted(filter(lambda x: x < 0, tmp))[:k - left - right]
		ans = max(ans, sum(tmp) - sum(m))
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for a in range(k + 1):
	for b in range(k + 1):
		if a + b > n or a + b > k:
			break
		c = k - a - b
		g = v[:a] + v[n - b:]
		g.sort()
		for i in range(min(c, a + b)):
			if g[i] < 0:
				g[i] = 0
		ans = max(ans, sum(g))
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):
		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 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)


import bisect
(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 - i):
		if i + j > n:
			break
		A = sorted(V[:i] + V[n - j:])
		a = min(k - i - j, bisect.bisect_left(A, 0))
		ans = max(ans, sum(A[a:]))
print(ans)


from itertools import chain, islice
R = lambda : map(int, input().split())
(n, k) = R()
v = list(R())
a = sorted(((x, i) for (i, x) in enumerate(v) if x < 0))
ans = max((sum((v[m] for m in chain(range(i - j), range(n - j, n)))) - sum(islice((x for (x, m) in a if m < i - j or m >= n - j), k - i)) for i in range(1, min(n, k) + 1) for j in range(i)))
print(ans)


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


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


import bisect
(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
R = min(N, K)
for r in range(R + 1):
	for a in range(r + 1):
		left = V[:a]
		b = r - a
		if b == 0:
			right = []
		else:
			right = V[-b:]
		v = left + right
		v.sort()
		n_nega = bisect.bisect_left(v, 0)
		k = min(n_nega, K - r)
		ans = max(ans, sum(v[k:]))
print(ans)


from itertools import *
(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(k + 1):
	if i > n:
		break
	for j in range(i + 1):
		c = 0
		d = sorted(v[:j] + v[n - i + j:])
		l = k - len(d)
		for m in d:
			if m < 0 and l:
				l -= 1
				continue
			c += m
		ans = max(ans, c)
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 *
(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)


def resolve():
	(N, K) = list(map(int, input().split()))
	V = list(map(int, input().split()))
	r = 0
	for i in range(min(N, K) + 1):
		for j in range(min(N - i, K - i) + 1):
			a = V[:i] + V[N - j:]
			b = [x for x in a if x < 0]
			b.sort()
			rij = sum(a) - sum(b[:K - i - j])
			r = max(r, rij)
	print(r)
resolve()


import sys
sys.setrecursionlimit(10 ** 9)

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 collections import deque
from heapq import heapify, heappop, heappush

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

def __starting_point():
	solve()
__starting_point()


(N, K) = map(int, input().split())
Vs = list(map(int, input().split()))
ans = 0
for x in range(1, min(K, N) + 1):
	for i in range(x + 1):
		Ts = Vs[:i] + Vs[N - (x - i):]
		sumOut = sum(Ts)
		Ts.sort()
		for T in Ts[:K - x]:
			if T < 0:
				sumOut -= T
			else:
				break
		ans = max(ans, sumOut)
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for left in range(k + 1):
	for right in range(k - left + 1):
		if left + right > n:
			continue
		for trash in range(k - left - right + 1):
			x = sorted(v[0:left] + v[::-1][0:right])[trash:]
			ans = max(ans, sum(x))
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
valu = []
for a in range(min(N, K) + 1):
	for b in range(min(N, K) - a + 1):
		val = sorted(V[:a] + V[N - b:])
		n = K - (a + b)
		for i in range(n):
			if len(val) > 0:
				if val[0] < 0:
					val.pop(0)
				else:
					break
		valu.append(sum(val))
print(max(valu))


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for l in range(n):
	for r in range(l, n + 1):
		toru = l + n - r
		if toru > k:
			continue
		li = v[:l]
		li.extend(v[r:])
		li.sort()
		s = sum(li)
		cnt = 0
		while toru < k and len(li) > cnt:
			if li[cnt] >= 0:
				break
			toru += 1
			s -= li[cnt]
			cnt += 1
		ans = max(ans, s)
		if s == 19:
			print(l, r)
print(ans)


import bisect
(N, K) = map(int, input().split())
V = list(map(int, input().split()))
sV = sorted(V)
ans = 0
for i in range(N):
	for j in range(N - i + 1):
		if i + j <= K:
			if i + j >= N:
				L = sV
			else:
				L = V[:i] + V[N - j:]
				L.sort()
			k = bisect.bisect_left(L, 0)
			kans = sum(L[min(max(0, K - i - j), k):])
			ans = max(ans, kans)
print(ans)


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


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


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


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


from sys import stdin
input = stdin.readline
(N, K) = map(int, input().split())
V = list(map(int, input().split()))
targ = min(N, K)
ans = -float('inf')
for i in range(targ + 1):
	for j in range(targ + 1 - i):
		get = sorted(V[:i] + V[N - j:])
		tmp = sum(get)
		for k in range(min(K - i - j, i + j)):
			tmp = max(tmp, tmp - get[k])
		ans = max(tmp, ans)
print(ans)


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


from bisect import bisect_left as bil
(N, K, *V) = map(int, open(0).read().split())
k = min(N, K)
ans = 0
for i in range(k + 1):
	for j in range(k - i + 1):
		U = V[:i] + V[-j:] if j != 0 else V[:i]
		U.sort()
		z = min(bil(U, 0), K - i - j)
		sm = sum(U[z:])
		if ans < sm:
			ans = sm
print(ans)


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


(n, k) = map(int, input().split())
d = list(map(int, input().split()))
ans = 0
for l in range(min(n, k) + 1):
	for r in range(min(n - l, k - l) + 1):
		tl = d[:l] + d[-r:] if r > 0 else d[:l]
		tk = k - l - r
		s = 0
		for t in sorted(tl):
			if t < 0 and tk > 0:
				s += -t
				tk -= 1
			ans = max(ans, sum(tl) + s)
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for i in range(1, min(N + 1, K + 1)):
	for j in range(i + 1):
		values = sorted(V[:j] + V[N - (i - j):])
		k = i + 1
		while k <= K and len(values) > 0 and (values[0] < 0):
			k += 1
			values.pop(0)
		ans = max(ans, sum(values))
print(ans)


(N, K) = [int(i) for i in input().split()]
V = [int(i) for i in input().split()]
M = min(N, K)
ma = 0
for l in range(M + 1):
	for r in range(M - l + 1):
		G = V[:l] + V[N - r:]
		G.sort()
		for i in range(K - l - r + 1):
			ma = max(ma, sum(G[i:]))
print(ma)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
m = min(n, k)
result = 0
for i in range(m + 1):
	for j in range(i + 1):
		t = v[:j]
		t.extend(v[n - (i - j):])
		t.sort(reverse=True)
		l = k - i
		while len(t) > 0 and l > 0 and (t[-1] < 0):
			t.pop()
			l -= 1
		result = max(result, sum(t))
print(result)


(n, k) = map(int, input().split())
v = [int(e) for e in input().split()]
m = min(n, k)
result = 0
for i in range(m + 1):
	for j in range(i + 1):
		t = v[:j]
		t.extend(v[n - (i - j):])
		t.sort()
		l = k - i
		while len(t) > 0 and l > 0 and (t[0] < 0):
			t.pop(0)
			l -= 1
		m = sum(t)
		if m > result:
			result = m
print(result)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for i in range(1, min(N, K) + 1):
	for j in range(i + 1):
		W = sorted(V[:j] + V[N - i + j:])
		for k in range(min(i, K - i) + 1):
			ans = max(ans, sum(W[k:]))
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
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:]
		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) = [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)


(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
KN = min(K, N)
for i in range(1, KN + 1):
	for j in range(i + 1):
		rec = V[:i - j] + V[N - j:]
		rec.sort(reverse=True)
		away = max(min(i, K - i), 0)
		for l in range(away + 1):
			recsum = sum(rec[:i - l])
			if recsum > ans:
				ans = recsum
print(ans)


(N, K) = map(int, input().split())
v = list(map(int, input().split()))
res = []
for i in range(K + 1):
	for j in range(K - i + 1):
		_v = v[:]
		stock = []
		stock.extend(_v[:i])
		_v = _v[i:]
		_v.reverse()
		stock.extend(_v[:j])
		stock.sort()
		for k in range(K - i - j + 1):
			res.append(sum(stock[k:]))
print(max(res))


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
ret = 0
for a in range(N):
	for b in range(N - a + 1):
		cmax = K - a - b
		if cmax >= 0:
			W = A[:a] + A[N - b:]
			W.sort()
			tmp = 0
			for i in range(len(W)):
				if i < cmax and W[i] < 0:
					continue
				else:
					tmp = sum(W[i:])
					break
			ret = max(ret, tmp)
print(ret)


(N, K) = map(int, input().split())
V = [int(i) for i in input().split()]
V2 = V[::-1]
R = min(N, K)
ans = 0
for a in range(R + 1):
	for b in range(R - a + 1):
		c = K - (a + b)
		t = 0
		for v in sorted(V[:a] + V2[:b]):
			if v < 0 and c > 0:
				c -= 1
				continue
			t += v
		ans = max(t, ans)
print(ans)


from itertools import combinations
from bisect import bisect_left
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for (i, j) in combinations(range(N + 2), 2):
	l = sorted(A[0:i] + A[j - 1:N])
	if len(l) <= K:
		m = bisect_left(l, 0)
		ans = max(ans, sum(l[min(K - len(l), m):]))
print(ans)


(n, k, *v) = map(int, open(0).read().split())
print(max((sum(sorted(v[:j] + v[n - i + j:])[min(sum((x < 0 for x in v[:j] + v[n - i + j:])), k - i):]) for i in range(min(n, k) + 1) for j in range(i + 1))))


(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,) = map(int, input().split())
ans = 0
for l in range(min(N, K + 1)):
	for r in range(min(N - l + 1, K - l + 1)):
		h = V[:l] + V[N - r:]
		h.sort(reverse=True)
		for _ in [0] * (K - (l + r)):
			if h and h[-1] < 0:
				h.pop()
		ans = max(ans, sum(h))
print(ans)


(N, K) = map(int, input().split())
V = [int(v) for v in input().split()]
ans = 0
for i in range(min(N + 1, K + 1)):
	que1 = V[:i]
	for j in range(min(N + 1 - i, K + 1 - i)):
		que2 = que1 + V[N - j:]
		que2.sort()
		for k in range(min(K + 1 - i - j, i + j + 1)):
			ans = max(ans, sum(que2[k:]))
print(ans)


import sys
(N, K) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(1, min(K, N) + 1):
	for j in range(i + 1):
		x = [v[k] for k in range(j)] + [v[k] for k in range(N - i + j, N)]
		tmp = sum(x)
		x.sort()
		for k in range(min(i, K - i)):
			if x[k] < 0:
				tmp -= x[k]
		if tmp > ans:
			ans = tmp
print(ans)


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)


([n, k], li) = [list(map(int, i.split())) for i in open(0)]
ans = 0
for i in range(1, min(n + 1, k + 1)):
	for j in range(i + 1):
		l = li[:i - j] + li[n - j:]
		re_num = min(k - i, len(l))
		l.sort()
		f = 0
		for p in range(re_num):
			if l[p] > 0:
				break
			f += 1
		l = l[f:]
		ans = max(ans, sum(l))
print(ans)


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


def sum0(L, k):
	c = 0
	for i in L:
		if i >= 0:
			c += i
		elif k > 0:
			k -= 1
		else:
			c += i
	return c
(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 + 1 - i):
		L = sorted(V[:i] + V[n - j:])
		ans = max(ans, sum0(L, k - (i + j)))
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
sz = min(N, K)
for a in range(1 + sz):
	for b in range(1 + sz - a):
		taken = V[:a] + V[N - b:]
		taken.sort()
		for c in range(1 + min(K - a - b, a + b)):
			score = sum(taken[c:])
			ans = max(ans, score)
print(ans)


(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) = map(int, input().split())
A = list(map(int, input().split()))
ans = -10 ** 7
for i in range(min(N, K) + 1):
	for j in range(min(N, K) + 1 - i):
		if j == 0:
			st = A[:i]
		else:
			st = A[:i] + A[-j:]
		st.sort(reverse=1)
		for suteru in range(K - i - j + 1):
			ans = max(ans, sum(st[:i + j - suteru]))
print(ans)


(N, K) = map(int, input().split())
v = list(map(int, input().split()))
w = v[::-1]
res = 0
for l in range(N + 1):
	for r in range(N + 1):
		if l + r > N or l + r > K:
			break
		x = sorted(v[:l] + w[:r])
		for i in range(l + r):
			if x[i] > 0 or i == K - l - r:
				res = max(res, sum(x[i:]))
				break
print(res)


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


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
(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) = list(map(int, input().split()))
V = list(map(int, input().split()))
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
		sum_ = sum(V[:left]) + sum(V[right:])
		have_minus = [num for num in V[:left] + V[right:] if num < 0]
		have_minus.sort()
		d = max(0, K - (len(V[:left]) + len(V[right:])))
		for i in range(min(d, len(have_minus))):
			sum_ -= have_minus[i]
		max_v = max(max_v, sum_)
print(max_v)


from itertools import accumulate
(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for l in range(min(n, k) + 1):
	for r in range(min(n, k) - l + 1):
		bag = sorted(v[:l] + v[n - r:])
		minus = sum((vi for vi in bag[:k - l - r] if vi < 0))
		ans = max(ans, sum(bag) - minus)
print(ans)


from bisect import bisect_left
(N, K) = map(int, input().split())
V = list(map(int, input().split()))
vmax = -10 ** 9
for n in range(min(N, K) + 1):
	A = V[:n]
	for m in range(min(N, K) - n + 1):
		B = V[N - m:]
		B = sorted(A + B)
		ind = bisect_left(B, 0)
		k = min(K - m - n, ind)
		cnt = sum(B[k:])
		vmax = max(vmax, cnt)
print(vmax)


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


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
lim = min(n, k)
ans = [0]
for a in range(lim + 1):
	for b in range(lim - a + 1):
		hand = sorted(v[:a] + v[n - b:])
		hs = sum(hand)
		for i in range(min(k - a - b, a + b)):
			test = hand[i]
			if test < 0:
				hs -= test
		ans.append(hs)
print(max(ans))


(N, K) = list(map(int, input().split()))
V = list(map(int, input().split()))
ans = 0
for l in range(K + 1):
	for r in range(K - l + 1):
		if l + r > N:
			continue
		d = K - l - r
		now = 0
		having = []
		for i in range(l):
			now += V[i]
			having.append(V[i])
		for i in range(N - r, N):
			now += V[i]
			having.append(V[i])
		having.sort()
		for i in range(d):
			if i >= len(having):
				break
			if having[i] >= 0:
				break
			now -= having[i]
		ans = max(ans, now)
print(ans)


(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:]
				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()))
ret = 0
for s in range(n):
	for e in range(s, n + 1):
		t = k - (s + n - e)
		if t < 0:
			continue
		l = sorted(v[:s] + v[e:])
		u = 0
		while u < len(l) and u < t and (l[u] < 0):
			u += 1
		ret = max(ret, sum(l[u:]))
print(ret)


import heapq
(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for i in range(1, min(N, K) + 1):
	for t in range(i + 1):
		B = V[0:i - t] + V[N - t:N]
		total = sum(B)
		cut = 0
		for j in range(min(i, K - i)):
			heapq.heapify(B)
			cut = min(cut, cut + heapq.heappop(B))
		ans = max(ans, total - cut)
print(ans)


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


def solve(string):
	(n, k, *v) = map(int, string.split())
	ans = 0
	for i in range(k + 1):
		for j in range(k - i + 1):
			base = sorted(v[:i] + v[max(n - k + i + j, i):])
			ans = max(ans, sum([b for (l, b) in enumerate(base) if b >= 0 or j <= l]))
	return str(ans)
print(solve('\n'.join([input(), input()])))


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


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
c = min(n, k)
ans = 0
for a in range(c + 1):
	for b in range(c + 1 - a):
		w = v[:a] + v[n - b:]
		w.sort()
		for i in range(k - (a + b)):
			if len(w) > 0 and w[0] < 0:
				del w[0]
			else:
				break
		ans = max(ans, sum(w))
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)


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


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ret = 0
for l in range(min(n, k) + 1):
	for r in range(min(n, k) - l + 1):
		d = k - l - r
		g = sorted(v[:l] + v[n - r:])
		for i in range(min(d, len(g))):
			g[i] = max(0, g[i])
		ret = max(ret, sum(g))
print(ret)


from bisect import bisect
(n, K) = (int(i) for i in input().split())
v = [int(i) for i in input().split()]
ans = 0
for i in range(min(n, K) + 1):
	for j in range(i + 1):
		z = []
		for k in range(j):
			z.append(v[k])
		for k2 in range(i - j):
			z.append(v[-k2 - 1])
		z.sort()
		ans = max(ans, sum(z[min(bisect(z, 0), K - i):]))
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for L in range(min(N, K + 1)):
	for R in range(min(N - L, K - L) + 1):
		js = V[:L] + V[-R:] if R > 0 else V[:L]
		t = K - L - R
		s = 0
		for i in sorted(js):
			if i < 0 and t > 0:
				s += -i
				t -= 1
		ans = max(ans, sum(js) + s)
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
		for k in range(0, j):
			hp.push(v[k])
		for k in range(0, i - j):
			if n - 1 - k < j:
				break
			hp.push(v[n - 1 - k])
		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)


from collections import deque
import heapq

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


(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 = -10 ** 18
for l in range(min(n, k) + 1):
	for r in range(min(n, k) + 1):
		if l + r > n or l + r > k:
			continue
		trg = v[:l] + v[n - r:]
		trg.sort(reverse=True)
		for i in range(k - l - r + 1):
			ans = max(ans, sum(trg[:len(trg) - i]))
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())
vs = list(map(int, input().split()))
m = 0
r = min(n, k)
for a in range(r + 1):
	for b in range(r - a + 1):
		cd = k - (a + b)
		if b == 0:
			hold = sorted(vs[:a])
		else:
			hold = sorted(vs[:a] + vs[-b:])
		ap = hold[min(len([1 for x in hold if x < 0]), cd):]
		s = sum(ap)
		m = max(s, m)
print(m)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
c = min(n, k)
ans = 0
for a in range(c + 1):
	for b in range(c - a + 1):
		t = v[:a] + v[n - b:]
		t.sort()
		for i in range(k - (a + b)):
			if len(t) and t[0] < 0:
				t.pop(0)
		ans = max(ans, sum(t))
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
ret = 0
for a in range(N):
	for b in range(N - a + 1):
		cmax = K - a - b
		if cmax >= 0:
			W = A[:a] + A[N - b:]
			W.sort()
			c = min(sum([1 for i in W if i < 0]), cmax)
			ret = max(ret, sum(W[c:]))
print(ret)


(N, K) = map(int, input().split())
Vlist = list(map(int, input().split()))
ret = 0
for l in range(min(N, K) + 1):
	for r in range(min(N, K) - l + 1):
		tem = Vlist[:l] + Vlist[N - r:]
		tem = sorted(tem)
		tem[:K - l - r] = [max(0, i) for i in tem[:K - l - r]]
		score = sum(tem)
		if ret < score:
			ret = score
print(ret)


(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 - i + 1, k - i + 1)):
		a = v[:i] + v[n - j:]
		a.sort(reverse=True)
		for _ in range(k - i - j):
			if a and a[-1] < 0:
				a.pop()
		ans = max(ans, sum(a))
print(ans)


(N, K) = map(int, input().split())
V = [int(a) for a in input().split()]
INF = 1 << 50
ma = 0
for i in range(min(K, N) + 1):
	for j in range(i + 1):
		S = sorted(V[:j] + ([] if i == j else V[-(i - j):]))
		ma = max(ma, sum([max(S[t], 0 if t < K - i else -INF) for t in range(len(S))]))
print(ma)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
x = 0
for i in range(min(n, k + 1)):
	for j in range(min(n - i + 1, k - i + 1)):
		h = sorted(a[:i] + a[n - j:])[::-1]
		for _ in range(k - i - j):
			if h and h[-1] < 0:
				h.pop()
		x = max(x, sum(h))
print(x)


(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) = map(int, input().split())
a = [int(x) for x in input().split()]
mx = 0
for i in range(min(n, k + 1)):
	for j in range(min(k - i + 1, n - i + 1)):
		summa = 0
		b = []
		for t in range(i):
			b.append(a[t])
		for t in range(n - j, n):
			b.append(a[t])
		z = k - i - j
		b.sort()
		for x in b:
			if x < 0 and z > 0:
				z -= 1
			else:
				summa += x
		mx = max(mx, summa)
print(mx)


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


(N, K) = map(int, input().split())
V = [int(a) for a in input().split()]
able = min(N, K)
ans = 0
for a in range(able + 1):
	for b in range(able + 1 - a):
		if b == 0:
			have = V[:a]
		else:
			have = V[:a] + V[-b:]
		have.sort()
		for i in range(min(a + b, K - a - b) + 1):
			val = sum(have[i:])
			if ans < val:
				ans = val
print(ans)


(N, K) = map(int, input().split())
v = list(map(int, input().split()))
max_pick = min(K, N)
ans = 0
for left in range(max_pick + 1):
	for right in range(max_pick - left + 1):
		t = v[:left] + v[N - right:]
		m = sorted(filter(lambda x: x < 0, t))[:K - left - right]
		ans = max(ans, sum(t) - sum(m))
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
m = min(n, k)
ans = -10 ** 9
for l in range(m + 1):
	for r in range(m - l + 1):
		jry = v[:l] + v[-r:] if r >= 1 else v[:l]
		t = k - l - r
		s = 0
		for i in sorted(jry):
			if i < 0 and t > 0:
				s += -i
				t -= 1
		ans = max(ans, sum(jry) + s)
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
vrev = v[::-1]
vab = []
ans = 0
for i in range(min(n, k) + 1):
	for j in range(min(n, k) - i + 1):
		vab = v[:i] + vrev[:j]
		vab.sort()
		if len(vab) > 0 and vab[0] < 0:
			for l in range(min(k - len(vab), len(vab))):
				if vab[l] < 0:
					vab[l] = 0
		ans = max(ans, sum(vab))
print(ans)


(N, K) = list(map(int, input().split()))
V = list(map(int, input().split()))
ans = []
for left in range(N + 1):
	for right in range(N + 1):
		if left + right > N:
			break
		li = V[:left] + V[N - right:]
		li = sorted(li)
		d = K - left - right
		if d < 0:
			break
		c = sum(li)
		for i in range(min(d, len(li))):
			if li[i] < 0:
				c -= li[i]
			else:
				break
		ans.append(c)
print(max(ans))


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ma = 0
kaisu = min(n, k)
for a in range(kaisu + 1):
	for b in range(kaisu - a + 1):
		push = k - (a + b)
		li = v[:a] + v[n - b:]
		li.sort(reverse=True)
		for c in range(push):
			if li:
				if li[-1] < 0:
					li.pop()
		ma = max(ma, sum(li))
print(ma)


from bisect import bisect_left
(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(0, k + 1):
	for j in range(0, min(k, n) - i + 1):
		tmp = v[:i] + (v[-j:] if j else [])
		tmp.sort()
		idx = min(k - i - j, bisect_left(tmp, 0))
		ans = max(ans, sum(tmp[idx:]))
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
vmax = 0
for l in range(0, K + 1):
	for r in range(0, K - l + 1):
		if N < l + r:
			break
		tv = V[:l] + V[N - r:]
		tv.sort()
		for n in range(min(len(tv), K - (l + r))):
			if tv[n] < 0:
				tv[n] = 0
		vmax = max(vmax, sum(tv))
print(vmax)


(N, K) = map(int, input().split())
Vs = list(map(int, input().split()))
rs = []
for i in range(0, min(N, K) + 1):
	for j in range(0, min(N, K) - i + 1):
		k = max(0, K - i - j)
		Vs2 = Vs[:i] + Vs[N - j:]
		VsN = [v for v in Vs2 if v < 0]
		if len(VsN) < k:
			r = sum(Vs2) - sum(VsN)
		else:
			r = sum(Vs2) - sum(sorted(VsN)[:k])
		rs.append(r)
r = max(rs)
print(r)


R = lambda : map(int, input().split())
(n, k) = R()
v = list(R())
ans = 0
for i in range(1, min(n, k) + 1):
	for j in range(i):
		t = v[:i - j] + v[n - j:]
		ans = max(ans, sum(t) - sum(sorted((x for x in t if x < 0))[:k - i]))
print(ans)


(N, K) = 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):
		items = V[:a] + V[N - b:]
		items.sort()
		for c in range(K - a - b + 1):
			ans = max(ans, sum(items[c:]))
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) = 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) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
from heapq import heapify, heappop
for j in range(1, min(N, K) + 1):
	for k in range(j + 1):
		x = V[:k] + V[N - j + k:]
		heapify(x)
		b = K - j
		while len(x) > 0 and x[0] < 0 and (b > 0):
			heappop(x)
			b -= 1
		ans = max(ans, sum(x))
print(ans)


(n, k) = [int(i) for i in input().split()]
v = [int(i) for i in input().split()]
res = 0
for right in range(k + 1):
	for left in range(min(n, k) - right + 1):
		ans = []
		ans += v[:right]
		ans += v[n - left:]
		ans.sort()
		for i in range(min(k - right - left, len(ans)) + 1):
			res = max(res, sum(ans[i:]))
print(res)


(n, k) = map(int, input().split())
V = list(map(int, input().split()))
ans = -10 ** 19
for i in range(min(k + 1, n + 1)):
	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) = 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)


(N, K) = map(int, input().split())
V = [int(i) for i in input().split()]
ans = 0
for i in range(N):
	for j in range(i, N + 1):
		c = 0
		if i + N - j <= K:
			k = K - (i + N - j)
			s = V[:i] + V[j:]
			s.sort()
			c = 0
			for t in s:
				if k >= 1 and t < 0:
					k -= 1
				else:
					c += t
		ans = max(c, ans)
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
r = min(n, k)
ans = -10 ** 10
for i in range(0, r + 1):
	for a in range(i + 1):
		b = i - a
		val = sorted(v[:a] + v[n - b:])
		s = sum(val)
		for j in range(min(k - i, len(val))):
			if val[j] < 0:
				s -= val[j]
			else:
				break
		ans = max(ans, s)
print(ans)


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


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


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = float('-inf')
for l in range(min(N + 1, K + 1)):
	for r in range(min(N - l + 1, K - l + 1)):
		arr = V[:l] + V[N - r:]
		t = sum(arr)
		arr.sort()
		for i in range(min(l + r, K - l - r)):
			a = arr[i]
			if a >= 0:
				break
			t -= a
		ans = ans if ans > t else t
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)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
r = min(n, k)
get = []
M = 0
for i in range(r + 1):
	for j in range(i + 1):
		get += v[0:j] + v[n - i + j:n]
		get.sort()
		R = min(i, k - i)
		for cd in range(0, R + 1):
			M = max(M, sum(get[cd:i]))
		get = []
print(M)


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)
			ans = max(ans, pv + sum(mv))
	print(max(0, ans))

def __starting_point():
	solve()
__starting_point()


(n, k, *V) = map(int, open(0).read().split())

def calc(i, j, k):
	W = sorted(V[:i] + V[:-j - 1:-1], reverse=True)
	for _ in range(k):
		if W[-1] < 0:
			W.pop()
	return sum(W)
ans = 0
r = min(n, k) + 1
for i in range(r):
	for j in range(r - i):
		for k_ in range(min(i + j, k + 1 - i - j)):
			ans = max(ans, calc(i, j, k_))
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
m = min(n, k)
for i in range(m + 1):
	for j in range(m - i + 1):
		t = v[:i] + v[n - j:]
		t.sort()
		d = tuple(filter(lambda x: x < 0, t))[:k - i - j]
		ans = max(ans, sum(t) - sum(d))
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) = 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
		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
		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) = 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, 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) = 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())
d = list(map(int, input().split()))
d = d * 2
ans = 0
for i in range(1, min(k + 1, n + 1)):
	for j in range(i + 1):
		have = [d[n + c - j] for c in range(i)]
		have.sort()
		if i != k:
			for h in range(k - i):
				if have == [] or have[0] >= 0:
					break
				del have[0]
		if sum(have) > ans:
			ans = sum(have)
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)
ans = []
take_V = []
if V_sorted[-1] <= 0:
	ans = 0
else:
	take_num = min(K, N)
	for tak in range(1, take_num + 1):
		reverse = min(K - tak, tak)
		for lef in range(tak + 1):
			for rev in range(reverse + 1):
				take = []
				rig = N - (tak - lef)
				take.extend(V[:lef])
				take.extend(V[rig:])
				take.sort()
				take_V.append(sum(take[rev:]))
	ans = max(take_V)
print(ans)


(n, k, *a) = 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 filter(lambda x: x > 0, b)))
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)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
res = []
for x in range(min(n, k) + 1):
	for a in range(x + 1):
		b = x - a
		l = v[:a]
		r = v[n - b:]
		z = []
		for t in l:
			if t < 0:
				z.append(-t)
		for t in r:
			if t < 0:
				z.append(-t)
		z.sort()
		z = z[::-1]
		res.append(sum(l) + sum(r) + sum(z[:k - x]))
print(max(res))


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


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for l in range(n):
	for r in range(n - l + 1):
		if l + r > k:
			break
		nv = v[:l] + v[n - r:]
		nv.sort()
		for i in range(k - l - r):
			if not nv or nv[0] >= 0:
				break
			del nv[0]
		ans = max(ans, sum(nv))
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
kk = k
k = min(n, k)
ans = 0
for i in range(k + 1):
	for j in range(k - i + 1):
		L = v[:i]
		R = v[-j:]
		if len(R) == n:
			R = []
		LR = L + R + [0]
		LR.sort()
		zero_idx = min(LR.index(0), kk - i - j)
		ans = max(ans, sum(LR[zero_idx:]))
print(ans)


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])
	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
			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]
					m = 0
					mcnt = 0
					while mcnt < l:
						if i < vv[m][0] and vv[m][0] < jj:
							m += 1
							continue
						own -= vv[m][1]
						mcnt += 1
						m += 1
					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])
	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]
			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
			maxown = max(own, maxown)
	return maxown

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


(N, K) = map(int, input().split())
List = list(map(int, input().split()))
ans = [0]
for i in range(min(N, K) + 1):
	for j in range(min(N, K) - i + 1):
		if j == 0:
			temp = List[:i]
		else:
			temp = List[:i] + List[-j:]
		for k in range(min(i + j, K - (i + j)) + 1):
			ans.append(sum(sorted(temp)[k:]))
print(max(ans))


(N, K) = map(int, input().split(' '))
V = list(map(int, input().split(' ')))
maxcost = min(N, K)
o = []
A = 0
while A <= maxcost:
	B = 0
	while A + B <= maxcost:
		a = V[:A] + V[N - B:]
		b = sorted(list(filter(lambda x: x < 0, a)))[:K - A - B]
		o.append(sum(a) - sum(b))
		B += 1
	A += 1
print(max(o))


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
M = min(N, K)
ans = 0
for i in range(1, M + 1):
	for a in range(i + 1):
		L = sorted(V[:a] + V[N - (i - a):], reverse=True)
		for _ in range(K - i):
			if L and L[-1] < 0:
				L.pop()
			else:
				break
		ans = max(ans, sum(L))
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)


(N, K) = map(int, input().split())
Vs = list(map(int, input().split()))
max_v = 0
R = min(N, K)
for r in range(R + 1):
	for a in range(r + 1):
		b = r - a
		inh = sorted(Vs[:a] + Vs[N - b:])
		for d in range(min(r, K - r) + 1):
			max_v = max(max_v, sum(inh[d:]))
print(max_v)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
res = 0
for l in range(K + 1):
	for r in range(K + 1 - l):
		if l + r > N:
			continue
		t = V[:l] + V[N - r:]
		t.sort()
		S = sum(t)
		for c in range(min(K - l - r, l + r)):
			if t[c] < 0:
				S -= t[c]
		res = max(res, S)
print(res)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = max((sum(sorted(V[:a] + V[N - b:])[c:]) for a in range(min(N, K) + 1) for b in range(min(N, K) - a + 1) for c in range(min(K - a - b, a + b) + 1)))
print(ans)


(n, k) = map(int, input().split())
(*V,) = map(int, input().split())
M = [v if v < 0 else 0 for v in V]
S = [0]
for i in range(1, min(k + 1, n + 1)):
	for j in range(i + 1):
		s = sum(V[:i - j]) + sum(V[n - j:])
		M_sub = sorted(M[:i - j] + M[n - j:])
		s -= sum(M_sub[:k - i])
		S += [s]
print(max(S))


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(1, k + 1):
	if i > n:
		break
	for j in range(i):
		tmpv = v[-j:] + v
		newv = tmpv[:i]
		newv.sort()
		rmsum = 0
		for t in range(min(k - i, len(newv))):
			if newv[t] < 0:
				rmsum += newv[t]
		ans = max(sum(newv) - rmsum, ans)
print(ans)


(n, k, *l) = map(int, open(0).read().split())
(v, m) = (0, min(n, k) + 1)
from bisect import *
for i in range(m):
	for j in range(m - i):
		s = sorted(l[:i] + l[n - j:])
		v = max(v, sum(s[min(bisect(s, -1), k - i - j):]))
print(v)


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


(n, k) = map(int, input().split())
targ = min(n, k)
v = list(map(int, input().split()))
ans = -10 ** 18
for i in range(targ + 1):
	for j in range(targ - i + 1):
		nl = v[:i] + v[n - j:]
		nl.sort()
		tmp = sum(nl)
		for t in range(min(k - (i + j), i + j)):
			tmp = max(tmp, tmp - nl[t])
		ans = max(tmp, ans)
print(ans)


import bisect

def main():
	(N, K) = map(int, input().split())
	V = list(map(int, input().split()))
	m = 0
	for i in range(min(N, K) + 1):
		for j in range(min(K - i, N - i) + 1):
			t = V[:i] + V[N - j:]
			t.sort()
			ind = bisect.bisect_right(t, 0)
			d = min(i + j, K - i - j, ind)
			m = max(m, sum(t[d:]))
	print(m)
main()


(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) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for a in range(50):
	for b in range(50):
		if a + b <= min(n, k):
			li = v[:a] + v[n - b:]
			sumv = sum(li)
			li.sort()
			for i in range(min(k - a - b, len(li))):
				if li[i] < 0:
					li[i] = 0
				else:
					break
			ans = max(ans, sum(li))
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):
		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)


(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()))
KK = K
K = min(N, K)
ans = 0
for k in range(1, K + 1):
	for i in range(k + 1):
		R = V[-(k - i):]
		if len(R) == N:
			R = []
		L = V[:i] + R + [0]
		L.sort()
		zero_index = min(L.index(0), KK - k)
		res = sum(L[zero_index:])
		ans = max(ans, res)
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for x in range(k + 1):
	for y in range(k - x + 1):
		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)


(n, k) = map(int, input().split())
v = [int(i) for i in input().split()]
jewel = []
ans = 0
for i in range(min(k + 1, n + 1)):
	for j in range(min(k - i + 1, n - i + 1)):
		jewel = v[:i] + v[:-(j + 1):-1]
		jewel.sort()
		temp = sum(jewel)
		leng = len(jewel)
		for m in range(k - i - j):
			if leng > m and jewel[m] < 0:
				temp += -jewel[m]
		ans = max(ans, temp)
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
cmax = 0
for k in range(1, min(K, N) + 1):
	for i in range(k + 1):
		A = V[:i] + V[N - (k - i):]
		A = sorted(A, reverse=True)
		a = min(k, K - k)
		for j in range(a):
			if A[-1] < 0:
				A.pop()
		cmax = max(cmax, sum(A))
print(cmax)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
t = min(n, k)
ans = 0
for i in range(t + 1):
	for j in range(t - i + 1):
		hnd = v[:i] + v[-j:] * (j != 0)
		hnd.sort(reverse=True)
		for _ in range(min(k - i - j, len(hnd))):
			if hnd[-1] < 0:
				hnd.pop()
			else:
				break
		cur = sum(hnd)
		if ans < cur:
			ans = cur
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
R = min(N, K)
M = 0
for a in range(0, R + 1):
	for b in range(0, R - a + 1):
		left = V[0:a]
		right = V[N - b:N]
		getV = sorted(left + right)
		for k in range(K - (a + b)):
			if getV != [] and getV[0] < 0:
				getV = getV[1:]
		sumGetV = sum(getV)
		if sumGetV > M:
			M = sumGetV
print(M)


import bisect
(N, K) = list(map(int, input().split()))
V = list(map(int, input().split()))
ans = 0
for i in range(1, K + 1):
	nownow = 0
	for p in range(i + 1):
		if i < N:
			now = sorted(V[:p] + V[p + N - i:])
		else:
			now = V
		index = bisect.bisect_right(now, 0)
		if K - i >= index:
			nownow = sum(now[index:])
		else:
			nownow = sum(now[K - i:])
		ans = max(ans, nownow)
print(ans)


import bisect
(N, K) = map(int, input().split())
V = [int(i) for i in input().split()]
ans = -10 ** 20
for l in range(min(K + 1, N + 1)):
	for r in range(min(K - l + 1, N - l + 1)):
		P = V[:l] + V[N - r:]
		P.sort()
		z = bisect.bisect_left(P, 0)
		if z <= K - l - r:
			ans = max(ans, sum(P[z:]))
		else:
			ans = max(ans, sum(P[K - l - r:]))
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
Q = min(N, K) + 1
res = 0
for a in range(Q):
	for b in range(Q - a):
		W = V[:a] + V[N - b:]
		W.sort()
		for k in range(min(K - a - b, len(W))):
			if W[k] < 0:
				W[k] = 0
			else:
				break
		res = max(res, sum(W))
print(res)


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) = 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) = map(int, input().split())
V = list(map(int, input().split()))
s = 0
for i in range(K + 1):
	for j in range(K + 1 - i):
		if i + j > N:
			continue
		a = V[:i] + V[N - j:]
		r = K - i - j
		a.sort()
		for k in range(min(len(a) + 1, r + 1)):
			s = max(s, sum(a[k:]))
print(s)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(k + 1):
	l = min(k - i, n)
	for a in range(l + 1):
		b = l - a
		if b == 0:
			sub = v[:a]
		else:
			sub = v[:a] + v[-b:]
		h = min(len(sub), i)
		for j in range(h):
			m = min(sub)
			if m < 0:
				sub.remove(m)
		ans = max(ans, sum(sub))
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) = map(int, input().split())
v = list(map(int, input().split()))
import bisect
ans = 0
for i in range(k):
	for j in range(min(n - i, k - i) + 1):
		u = v[:j] + v[n - i:]
		u.sort()
		ind = bisect.bisect_left(u, 0)
		t = min(ind, k - i - j)
		sm = sum(u[t:])
		if ans < sm:
			ans = sm
print(ans)


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


import bisect
(N, K) = map(int, input().split())
V = [int(i) for i in input().split()]
ans = 0
for a in range(min(N, K) + 1):
	for b in range(min(N, K) - a + 1):
		score = 0
		D = sorted(V[:a] + V[N - b:])
		score = sum(D[min(K - (a + b), bisect.bisect_left(D, 0)):])
		ans = max(ans, score)
print(ans)


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

def query(l, r):
	if l + r > K:
		return 0
	rest = K - l - r
	lst = V[:l] + V[N - r:]
	lst.sort()
	return sum([x for (i, x) in enumerate(lst) if x > 0 or i >= rest])
ans = 0
for l in range(N + 1):
	for r in range(N + 1 - l):
		ans = max(ans, query(l, r))
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
u = v[::-1]
ans = 0
m = min(n, k)
for l in range(m + 1):
	for r in range(m - l + 1):
		s = v[:l] + u[:r]
		s.sort()
		for i in range(k - l - r + 1):
			ans = max(ans, sum(s[i:]))
print(ans)


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


(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 - i + 1):
		if i + j > k:
			continue
		tmp = V[:i] + V[n - j:]
		tmp.sort(reverse=True)
		for l in range(k - i - j):
			if tmp and tmp[-1] < 0:
				tmp.pop()
			else:
				break
		ans = max(ans, sum(tmp))
print(ans)


(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):
		a = []
		if l + r > N:
			break
		a = V[:l]
		a.extend(V[N - r:])
		b = sum(a)
		a.sort()
		for i in range(min(K - l - r, l + r)):
			if a[i] >= 0:
				break
			else:
				b -= a[i]
		ans = max(ans, b)
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)


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()))
results = []
for a in range(n + 1):
	for b in range(min(n - a, k - a) + 1):
		p = v[:a] + v[n - b:]
		p.sort()
		for i in range(k - a - b + 1):
			results.append(sum(p[i:]))
print(max(results))


import heapq
import copy
(N, K) = map(int, input().split())
V_list = list(map(int, input().split()))
selected = []
left = []
max_sum = 0
left_sum = 0
for l in range(N):
	selected = copy.deepcopy(left)
	lr_sum = left_sum
	for r in range(N - l + 1):
		stock = K - l - r
		if stock < 0:
			break
		ri = N - r - 1
		select_cnt = len(selected)
		tmp_sum = lr_sum
		max_sum = max(max_sum, tmp_sum)
		popper = copy.deepcopy(selected)
		for i in range(stock):
			if i >= select_cnt:
				break
			pop_v = heapq.heappop(popper)
			if pop_v > 0:
				break
			tmp_sum -= pop_v
			max_sum = max(max_sum, tmp_sum)
		r_val = V_list[ri]
		lr_sum += r_val
		heapq.heappush(selected, r_val)
	l_val = V_list[l]
	left_sum += l_val
	heapq.heappush(left, l_val)
print(max_sum)


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


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


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


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


f = lambda : map(int, input().split())
(n, k) = f()
l = list(f())
v = 0
m = min(n, k)
from bisect import *
for i in range(m + 1):
	for j in range(m + 1 - i):
		s = sorted(l[:i] + l[n - j:])
		v = max(v, sum(s[min(bisect_left(s, 0), k - i - j):]))
print(v)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
best = 0
for i in range(min(n, k) + 1):
	for j in range(min(i + 1, k - i + 1)):
		for m in range(i + 1):
			out = list(v[0:m]) + list(v[:-(i - m + 1):-1])
			out.sort()
			best = max(best, sum(out[j:]))
print(best)


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 heappop, heapify
(N, K, *V) = list(map(int, open(0).read().split()))
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)


(N, K) = map(int, input().split())
V = [0] * N
(*V,) = map(int, input().split())
ans = []
for i in range(N + 1):
	for j in range(N + 1):
		if i + j > min(N, K):
			continue
		out = V[:i] + V[N - j:]
		out.sort()
		r = 0
		while i + j + r < K and r < len(out):
			if out[r] < 0:
				r += 1
			else:
				break
		ans.append(sum(out[r:]))
print(max(ans))


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
max_value = 0
for l in range(K + 1):
	for r in range(K + 1):
		if K < l + r or N < l + r:
			break
		hand = sorted(V[:l] + V[N - r:])
		for d in range(min(len(hand), K - l - r)):
			hand[d] = max(0, hand[d])
		max_value = max(max_value, sum(hand))
print(max_value)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for x in range(1, 1 + min(N, K)):
	for y in range(1 + min(x, K - x)):
		for z in range(1 + x):
			pick = V[:z]
			if z - x < 0:
				pick += V[z - x:]
			pick.sort()
			now = sum(pick[y:])
			ans = max(now, ans)
print(ans)


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


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
R = min(N, K)
for A in range(R + 1):
	for B in range(R - A + 1):
		s = V[:A] + V[N - B:]
		s.sort()
		S = sum(s)
		for k in range(min(K - A - B, len(s))):
			if s[k] < 0:
				S -= s[k]
		ans = max(ans, S)
print(ans)


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 bisect
(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 - i):
		if i > n - j:
			break
		now = sorted(v[:i] + v[n - j:])
		tmp = min(k - i - j, bisect.bisect_left(now, 0))
		ans = max(ans, sum(now[tmp:]))
print(ans)


(n, k) = map(int, input().split())
lst = list(map(int, input().split()))
ans = 0
m = min(n, k)
for a in range(m + 1):
	for b in range(m + 1 - a):
		jewel = lst[:a] + lst[n - b:]
		jewel.sort()
		for c in range(k + 1 - a - b):
			ans = max(ans, sum(jewel[c:]))
print(ans)


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)


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


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
import bisect
ans = 0
minnk = min(n, k)
for r in range(minnk + 1):
	for l in range(minnk + 1 - r):
		sute = k - (r + l)
		temoti = sorted(v[:l] + v[n - r:])
		n_nega = bisect.bisect(temoti, 0)
		score = sum(temoti[min(n_nega, sute):])
		if ans < score:
			ans = score
print(ans)


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)


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


(n, K) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for k in range(K + 1):
	for a in range(min(k, n) + 1):
		for b in range(min(k, n) - a + 1):
			V = v[:a] + v[n - b:]
			V.sort()
			if k - a - b <= a + b:
				ans = max(ans, sum(V[k - a - b:]))
print(ans)


(n, k, *v) = map(int, open(0).read().split())
ans = 0
for i in range(n + 1):
	for j in range(n + 1):
		if i + j > k:
			continue
		cand = sorted([v[I] for I in range(n) if I < i or n - j <= I])
		cnt = sum(cand)
		ans = max(ans, cnt)
		for l in range(min(k - i - j, len(cand))):
			cnt -= cand[l]
			ans = max(ans, cnt)
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
k = min(N, K)
v = 0
for i in range(k + 1):
	for j in range(k - i + 1):
		v_tmp = V[:i] + V[N - j:]
		v_tmp.sort()
		for l in range(K - (i + j) + 1):
			v = max(v, sum(v_tmp[l:]))
print(v)


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)


import math
from collections import deque
(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(1, min(k, n) + 1):
	for m in range(i + 1):
		s = v[:m] + v[n - (i - m):]
		s.sort()
		for j in range(i, min(k, 2 * i)):
			if s[j - i] < 0:
				s[j - i] = 0
		ans = max(ans, sum(s))
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for l in range(n + 1):
	for r in range(l, max(n, l + 1)):
		o = v[:l] + v[r + 1:]
		if len(o) > k:
			continue
		o.sort()
		i = 0
		while i < len(o) and i < k - len(o) and (o[i] < 0):
			i += 1
		ans = max(ans, sum(o[i:]))
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
answer = 0
limit = min(N, K)
for a in range(limit + 1):
	for b in range(limit - a + 1):
		for c in range(K - (a + b) + 1):
			use = V[:a] + V[N - b:]
			use.sort()
			s = sum(use[c:])
			answer = max(answer, s)
print(answer)


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)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
ans = []
for lhs in range(k + 1):
	for rhs in range(k - lhs + 1):
		if lhs + rhs <= n:
			array = v[:lhs] + v[n - rhs:]
		else:
			array = v[:]
		for i in range(k + 1 - lhs - rhs):
			array.sort()
			ans.append(sum(array[i:]))
print(max(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)


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()
	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):]
			temp = sorted(temp)
			for i3 in range(i1):
				if temp[i3] >= 0 or i3 >= k - i1:
					stop = i3
					break
				stop = 10 ** 9
			if stop != 10 ** 9:
				ans = max(sum(temp[i3:]), ans)
	print(ans)

def __starting_point():
	do()
__starting_point()


(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) = map(int, input().split())
V = list(map(int, input().split()))
R = min(N, K)
ans = 0
for i in range(R + 1):
	for j in range(R - i + 1):
		if i == 0 and j == 0:
			continue
		L = sorted(V[:i] + V[N - j:])
		k = min(K - i - j, len(L) - 1)
		for p in range(k):
			if L[p] >= 0:
				k = p
				break
		ans = max(ans, sum(L[k:]))
print(ans)


(N, K, *V) = list(map(int, open(0).read().split()))
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) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
min_nk = min(n, k)
for i in range(min_nk + 1):
	for j in range(n - min_nk + i, n + 1):
		count = a[0:i] + a[j:n]
		count.sort()
		ans = max(ans, sum(count))
		for x in range(1, k - len(count) + 1):
			ans = max(ans, sum(count[x:]))
print(ans)


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
max_cnt = -float('inf')
for k in range(min(N, K) + 1):
	for i in range(k + 1):
		j = k - i
		le = V[:i]
		ri = V[-j:] if j > 0 else []
		ne = [i for i in le if i < 0] + [j for j in ri if j < 0]
		ne.sort()
		max_cnt = max(sum(le) + sum(ri) - sum(ne[:K - k]), max_cnt)
print(max_cnt)


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

def __starting_point():
	abc128_d()
__starting_point()


(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for m1 in range(N + 1):
	for m2 in range(N - m1 + 1):
		for l in range(m1 + m2 + 1):
			if m1 + m2 + l > K:
				continue
			if m1 + m2 > N:
				continue
			tmp = V[0:m1] + V[N - m2:N]
			tmp.sort(reverse=True)
			ans = max(ans, sum(tmp[0:m1 + m2 - l]))
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)


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 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 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
				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
print(main())


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
idx_k = k
k = min(n, k)
ans = 0
for i in range(k + 1):
	for j in range(k - i + 1):
		a = v[:i]
		b = v[-j:]
		if len(b) == n:
			b = []
		ab = sorted(a + b + [0])
		idx = min(ab.index(0), idx_k - i - j)
		ans = max(ans, sum(ab[idx:]))
print(ans)


import heapq
import itertools

def main():
	(n, k) = list(map(int, input().split()))
	v = [int(i) for i in input().split()]
	v_1 = v[::-1]
	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()


from collections import deque
(N, K) = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for lk in range(min(K, N) + 1):
	for rk in range(min(K, N) + 1 - lk):
		k = K - lk - rk
		v = V[:lk] + V[N - rk:]
		v.sort()
		ans = max(sum(v[k:]) + sum([x for x in v[:k] if x > 0]), ans)
if K >= 2 * N:
	ans = sum([v for v in V if v >= 0])
print(ans)


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
mini = min(n, k)
value = 0
for a in range(mini + 1):
	for b in range(mini - a + 1):
		c = k - a - b
		j = v[:a] + v[n - b:]
		j.sort(reverse=True)
		for _ in range(c):
			if j and j[-1] < 0:
				j.pop()
			else:
				break
		value = max(value, sum(j))
print(value)


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()))
	ans = 0
	R = min(N, K)
	for i in range(R + 1):
		for j in range(R + 1 - i):
			tmp = 0
			q = []
			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()


(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) + 1 - A):
		hand = V[:A] + V[N - B:]
		hand.sort()
		i = 0
		while i < K - A - B and i < len(hand) and (hand[i] < 0):
			hand[i] = 0
			i += 1
		ans = max(ans, sum(hand))
print(ans)


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