Problem Description
Damian has an array A of N numbers, and wants to find the minimum contiguous sum that can be formed.
However, he decides that this is too trivial. Thus, he decides to swap up to K pairs of numbers first, in the hope of making the sum even smaller.
What is the new minimum sum possible?
Input
The first line contains two integers, N and K, the number of integers and the maximum number of swaps possible.
The second line contains N space-separated integers, representing the numbers of the array.
Output
The output should contain one line containing one integer, the minimum contiguous sum that can be formed.
Limits
For all subtasks, |Ai| ≤ 106; 1 ≤ N ≤ 100.
Subtask 1 (19%): K = 0.
Subtask 2 (27%): K = 1.
Subtask 3 (54%): 0 ≤ K ≤ 100.
Subtask 4 (0%): Sample Testcases.
Sample Testcase 1
Input
8 1
-1 5 -5 -3 2 -5 -4 0
Output
-18
Sample Testcase 1 Explanation
Damian swaps the number at position 0 with the number at position 4.
The minimum contiguous sum can then be formed in this way: 2 5 (-5 -3 -1 -5 -4 0)