2826: Sereja and Swaps
Time Limit: 2 Sec Memory Limit: 256 MBSubmit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]
Description
time limit per test
1 secondmemory limit per test
256 megabytesinput
standard inputoutput
standard outputAs 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?
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