As usual, Sereja has array a, its elements are integers: a[1], a[2], ..., a[n]. Let's introduce notation:

$f(a, l, r) = \sum_{i = l}^{r} a [ i ] ; m(a) = \operatorname{max}_{1 \leq l \leq r \leq n} f(a, l, r)$

A swap operation is the following sequence of actions:

  choose two indexes i, j (i ≠ j);  perform assignments tmp = a[i], a[i] = a[j], a[j] = tmp. 

What maximum value of function m(a) can Sereja get if he is allowed to perform at most k swap operations?


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 200; 1 ≤ k ≤ 10). The next line contains n integers a[1], a[2], ..., a[n] ( - 1000 ≤ a[i] ≤ 1000).


-----Output-----

In a single line print the maximum value of m(a) that Sereja can get if he is allowed to perform at most k swap operations.


-----Examples-----
Input
10 2
10 -1 2 2 2 2 2 2 -1 10

Output
32

Input
5 10
-1 -1 -1 -1 -1

Output
-1

Difficulty: MEDIUM
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
res = a[0]
for l in range(n):
	for r in range(l, n):
		inside = sorted(a[l:r + 1])
		outside = sorted(a[:l] + a[r + 1:], reverse=True)
		new_res = sum(inside)
		for i in range(min(k, len(inside), len(outside))):
			if outside[i] > inside[i]:
				new_res += outside[i] - inside[i]
			else:
				break
		if new_res > res:
			res = new_res
print(res)


(n, k) = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
best = max(A)
for left in range(n):
	for right in range(left, n):
		inner = A[left:right + 1]
		outer = A[:left] + A[right + 1:]
		inner.sort()
		outer.sort(reverse=True)
		for i in range(k):
			if i >= len(inner) or i >= len(outer):
				break
			if inner[i] < outer[i]:
				inner[i] = outer[i]
			else:
				break
		best = max(best, sum(inner))
print(best)


def solve(a, l, r, k):
	out = sorted(a[:l] + a[r:], reverse=True)
	inside = sorted(a[l:r])
	cur = sum(a[l:r])
	for i in range(min(k, len(inside), len(out))):
		if out[i] > inside[i]:
			cur += out[i] - inside[i]
		else:
			break
	return cur
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
assert len(a) == n
best = a[0]
for l in range(n):
	for r in range(l + 1, n + 1):
		cur = solve(a, l, r, k)
		if cur > best:
			best = cur
print(best)


from bisect import bisect_left, bisect_right
(n, k) = map(int, input().split())
t = list(map(int, input().split()))
p = sorted(t)
if p[-1] <= 0:
	print(p[-1])
	exit(0)
if p[0] >= 0:
	print(sum(p))
	exit(0)
i = max(0, n - k - 1)
while p[i] < 0:
	i += 1
q = sum(p[i:])
if n < k + 2 or p[n - k - 1] <= 0:
	print(q)
	exit(0)
for l in range(n - k - 2):
	r = l + k + 2
	u = sorted(t[:l] + t[r:])
	v = sorted(t[l:r])
	for i in range(r, n):
		q = max(q, sum(sorted(v + u[-min(k, len(u)):])[-len(v):]))
		u.remove(t[i])
		v.insert(bisect_left(v, t[i]), t[i])
	q = max(q, sum(sorted(v + u[-min(k, len(u)):])[-len(v):]))
print(q)


def readln():
	return tuple(map(int, input().split()))
(n, k) = readln()
a = list(readln())
ans = -10 ** 9
for i in range(n):
	for j in range(i, n):
		x = a[:i] + a[j + 1:]
		y = a[i:j + 1]
		x.sort()
		y.sort()
		x.reverse()
		for p in range(min(k, min(len(x), len(y)))):
			if x[p] > y[p]:
				(x[p], y[p]) = (y[p], x[p])
		ans = max(ans, sum(y))
print(ans)


__author__ = 'Lipen'

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = a[0]
	for l in range(n):
		for r in range(l, n):
			out = sorted(a[:l] + a[r + 1:], reverse=True)
			inside = sorted(a[l:r + 1])
			temp = sum(a[l:r + 1])
			for i in range(min(k, len(out), len(inside))):
				if out[i] > inside[i]:
					temp += out[i] - inside[i]
				else:
					break
			if temp > s:
				s = temp
	print(s)
main()


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

def solve(i, j):
	cur_res = sum(a[i:j + 1])
	a1 = sorted(a[i:j + 1])
	a2 = sorted(a[:i] + a[j + 1:], reverse=True)
	for t in range(min(k, len(a1), len(a2))):
		m = min(a1)
		if a2[t] > m:
			cur_res += a2[t] - m
			a1[a1.index(m)] = a2[t]
	return cur_res
print(max((solve(i, j) for i in range(n) for j in range(i, n))))


import os
if not 'BEFUNGEE_HOME' in os.environ.keys():
	f = open('input.txt', 'r')
	input = f.readline
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))

def f(l, r):
	original_sequence = a[l:r + 1]
	outside_sequence = a[:l] + a[r + 1:]
	original_sequence.sort()
	outside_sequence.sort(reverse=True)
	k_ = min(k, len(original_sequence), len(outside_sequence))
	original_sequence[:k_] = [max(x, y) for (x, y) in zip(original_sequence[:k_], outside_sequence[:k_])]
	s = sum(original_sequence)
	return s
result = -2000000
for l in range(n):
	for r in range(l, n):
		result = max(f(l, r), result)
print(result)


bot = True
read_line = lambda : [int(i) for i in input().split()]
(n, k) = read_line()
x = read_line()
print(max((sum(sorted(x[l:r] + sorted(x[:l] + x[r:])[-k:])[l - r:]) for l in range(n) for r in range(l + 1, n + 1))))


readline = lambda : [int(x) for x in input().split()]
(n, k) = readline()
a = readline()
best = max(a)
for left in range(n):
	for right in range(left, n):
		inner = a[left:right + 1]
		outer = a[:left] + a[right + 1:]
		inner.sort()
		outer.sort(reverse=True)
		for i in range(k):
			if i >= len(inner) or i >= len(outer):
				break
			if inner[i] < outer[i]:
				inner[i] = outer[i]
			else:
				break
		best = max(best, sum(inner))
print(best)


(n, k) = [int(c) for c in input().split()]
a = [int(c) for c in input().split()]
best = -1000001
seq = []
other = []
for l in range(n):
	for r in range(l + 1, n + 1):
		seq = sorted(a[l:r])
		other = a[:l] + a[r:]
		other.sort()
		other.reverse()
		seq_sum = sum(seq)
		best = max(best, seq_sum)
		for sw in range(0, min(k, len(seq), len(other))):
			seq_sum = seq_sum - seq[sw] + other[sw]
			best = max(best, seq_sum)
print(best)


import sys
R = lambda : list(map(int, input().split()))

def f(l, r):
	ans = sum(a[l:r + 1])
	a1 = sorted(a[l:r + 1])
	a2 = sorted(a[:l] + a[r + 1:], reverse=True)
	for i in range(min(k, len(a1), len(a2))):
		m = min(a1)
		if a2[i] > m:
			ans += a2[i] - m
			a1[a1.index(m)] = a2[i]
	return ans
(n, k) = R()
a = R()
print(max((f(l, r) for l in range(n) for r in range(l, n))))


R = lambda : map(int, input().split())
(n, k) = R()
a = list(R())

def f(l, r):
	x = sorted(a[:l] + a[r + 1:], reverse=True)
	y = sorted(a[l:r + 1])
	return sum(y + [max(0, x[i] - y[i]) for i in range(min(k, len(x), len(y)))])
print(max((f(l, r) for l in range(n) for r in range(l, n))))


def f(a, k):
	ans = -float('inf')
	for i in range(len(a) + 1):
		for j in range(i):
			mid = a[j:i]
			l = a[:j] + a[i:]
			l = sorted(l, reverse=True)
			mid = sorted(mid)
			s = sum(mid)
			ans = max(ans, s)
			kk = k
			while kk:
				if l and mid and (s - mid[0] + l[0] > s):
					s = s - mid[0] + l[0]
					l.pop(0)
					mid.pop(0)
					kk -= 1
					ans = max(ans, s)
				else:
					break
	return ans
(n, k) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
print(f(a, k))


(n, kr) = map(int, input().split())
l = list(map(int, input().split()))
ans = -2e+18
for i in range(n):
	for j in range(i, n):
		k = kr
		sub = l[i:j + 1]
		sub_sum = sum(sub)
		sub.sort()
		chk = l[0:i] + l[j + 1:]
		chk.sort()
		chk.reverse()
		ans = max(ans, sub_sum)
		for t in range(len(sub)):
			if t < len(chk) and k > 0:
				if sub[t] < chk[t]:
					sub_sum -= sub[t]
					sub_sum += chk[t]
					ans = max(ans, sub_sum)
					k -= 1
			else:
				break
print(ans)


(n, m) = map(int, input().split())
lis = list(map(int, input().split()))
k = -100000000
for l in range(n):
	for r in range(l + 1, n + 1):
		k = max(k, sum(sorted(lis[l:r] + sorted(lis[:l] + lis[r:])[-m:])[l - r:]))
print(k)


from operator import itemgetter
from sys import stdin, stdout

def solve(a, k):
	aa = list(map(lambda x: [x[1], x[0]], enumerate(a)))
	aa.sort(reverse=True, key=itemgetter(0))
	if aa[0][0] < 0:
		return aa[0][0]
	best = -float('inf')
	for i in range(len(a)):
		for j in range(1, len(a) + 1):
			in_range = sorted(a[i:j], reverse=True)
			out_of_range = sorted(a[:i] + a[j:])
			additional = []
			for kk in range(k):
				if len(out_of_range) > 0 and len(in_range) > 0 and (in_range[-1] < out_of_range[-1]):
					in_range.pop()
					additional.append(out_of_range.pop())
			best = max(best, sum(in_range + additional))
	return best

def __starting_point():
	(n, k) = map(int, stdin.readline().split())
	a = [int(x) for x in stdin.readline().split()]
	stdout.write('{}\n'.format(solve(a, k)))
__starting_point()


def solve(curr, other, k):
	t = 0
	while t < k and t < len(curr) and (t < len(other)) and (other[t] > curr[t]):
		t += 1
	return t
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
maxx = -10 ** 100
for i in range(n):
	curr = []
	other = sorted(arr[:i] + arr[i + 1:], reverse=True)
	for j in range(i, n):
		curr.append(arr[j])
		curr.sort()
		if j < n - 1:
			del other[other.index(arr[j + 1])]
		t = min(len(curr), len(other), k)
		t = solve(curr, other, k)
		maxx = max(maxx, sum(curr) - sum(curr[:t]) + sum(other[:t]))
print(maxx)