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

<image>

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
//package codeforces;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class A implements Closeable {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    A() throws IOException {
//        reader = new BufferedReader(new FileReader("input.txt"));
//        writer = new PrintWriter(new FileWriter("output.txt"));
    }

    StringTokenizer stringTokenizer;

    String next() throws IOException {
        while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
            stringTokenizer = new StringTokenizer(reader.readLine());
        }
        return stringTokenizer.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    private final int MOD = 1000 * 1000 * 1000 + 7;

    int sum(int a, int b) {
        a += b;
        return a >= MOD ? a - MOD : a;
    }

    int product(int a, int b) {
        return (int) (1l * a * b % MOD);
    }

    int pow(int x, int k) {
        int result = 1;
        while (k > 0) {
            if (k % 2 == 1) {
                result = product(result, x);
            }
            x = product(x, x);
            k /= 2;
        }
        return result;
    }

    int inv(int x) {
        return pow(x, MOD - 2);
    }

    void solve() throws IOException {
        int n = nextInt(), k = nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        Queue<Integer> minQ = new PriorityQueue<>(), maxQ = new PriorityQueue<>(n, Collections.reverseOrder());
        int answer = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j <= n; j++) {
                minQ.clear();
                maxQ.clear();
                for(int l = 0; l < i; l++) {
                    maxQ.add(a[l]);
                }
                int s = 0;
                for(int l = i; l < j; l++) {
                    minQ.add(a[l]);
                    s += a[l];
                }
                for(int l = j; l < n; l++) {
                    maxQ.add(a[l]);
                }
                for(int l = 0; !maxQ.isEmpty() && !minQ.isEmpty() && l < k; l++) {
                    if(maxQ.peek() > minQ.peek()) {
                        s += maxQ.poll() - minQ.poll();
                    }
                }
                answer = Math.max(answer, s);
            }
        }
        writer.println(answer);
    }

    public static void main(String[] args) throws IOException {
        try (A a = new A()) {
            a.solve();
        }
    }

    @Override
    public void close() throws IOException {
        reader.close();
        writer.close();
    }
}
