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

Starter code:

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


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


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

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])
    return
if p[0] >= 0:
    print(sum(p))
    return
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)
    return

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)

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)

# coding=utf-8
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)))

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


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


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

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



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



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



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



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



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



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



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



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])]
        #print(other)
        t=min(len(curr),len(other),k)
        t=solve(curr,other,k)
        maxx=max(maxx,sum(curr)-sum(curr[:t])+sum(other[:t]))
        #print(curr,other,sum(curr)-sum(curr[:t])+sum(other[:t]))
    #print(maxx)
    #print(curr,other)
print(maxx)

# Made By Mostafa_Khaled 
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)))


# Made By Mostafa_Khaled


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

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)

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): #check for k number of swaps for this combination
            if i>=len(inner) or i>=len(outer): break
            if inner[i]<outer[i]:
                inner[i]=outer[i] #don't give a swap fuck haha,,, bitch!
            else:
                break #no more chances
        best = max(best, sum(inner)) #results update
print(best)


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


# HEY STALKER
n, kr = map(int, input().split())
l = list(map(int, input().split()))
ans = -2e18
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)

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