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).
from typing import List

def maximum_value_of_function(n:int, k:int, a:List[int]) -> int:
    
    def swap(a,i,j):            # helper function to swap numbers in array for ith and jth index
        temp = a[i]
        a[i] = a[j]
        a[j] = temp
        return a

    def get_max(a):              # helper function to get the max value of the current array 
        sums = []
        current_sum = 0
        for val in a:
            if val>0:                            # if the current value is greater than 0 i.e. not negative then we add the val to current sum
                current_sum += val
            else:
                sums.append(current_sum)            # else if negative we append the value to the list of sums and set current_sum = 0
                current_sum = 0
        sums.append(current_sum)
        return max(sums)                             # we return the max of the list of sums

    def get_indexes(a,n):                   # helper function to get the indexes satisfying our question
        indexes = []
        counter = 0
        for index in range(0,len(a)):

            for sub_index in range(index,len(a)):

                if a[sub_index]<0:
                    counter += 1
                    if counter == n+1:
                        indexes.append((index,sub_index-1))
                        counter = 0
                        break
            indexes.append((index,sub_index))
            counter = 0


        return indexes
    
    indexes = get_indexes(a,k)
    sums = []
    for index in indexes:
        temp = list(a)

        for i in range(0,k):

            for sub_index in range(index[0],index[1]+1):

                if temp[sub_index]<0:

                    maxright = max(temp[index[1]+1:]) if temp[index[1]+1:] != [] else 0
                    maxleft = max(temp[:index[0]]) if temp[:index[0]] != [] else 0

                    if maxright>=maxleft and maxleft>=0 and maxright!=0:

                        temp = swap(temp,sub_index,temp.index(maxright))

                        break
                    elif maxleft>maxright and maxright>=0 and maxleft!=0:

                        temp = swap(temp,sub_index,temp.index(maxleft))

                        break
                    else:
                        break

        sums.append(get_max(temp))
    return max(sums) if max(sums) != 0 else -1
    
n, k = map(int, input().split())
a = map(int, input().split())
print(maximum_value_of_function(n,k,a))