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

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?
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).
import sys
n, k = map(int, input().split())
a = list(map(int, input().split()))
sums = [0] * (n + 1)
for i in range(n):
    sums[i] += sums[i - 1] + a[i]
maximum, maxl, maxr = -1005, 0, 0
for l in range(-1, n):
    for r in range(l + 1, n):
        if sums[r] - sums[l] > maximum:
            maxl = l
            maxr = r
            maximum = sums[r] - sums[l]
trint = sorted(a[maxl + 1:maxr + 1])
flint = sorted(a[:maxl + 1] + a[maxr + 1:], reverse=True)
for i in range(len(trint)):
    if not flint:
        break
    for j in range(len(flint) - 1, -1, -1):
        if i < len(trint) and j < len(flint) and trint[i] < flint[j]:
            trint[i] = flint.pop()
            k -= 1
            break
        else:
            flint = []
for i in range(len(trint)):
    if not k:
        break
    if trint[i] < 0 and len(trint) > 1:
        k -= 1
        trint[i] = 0
print(sum(trint))