You are given an array having N integers. You have to select at most K positions in the array and replace the values at those positions with 0 such that the sum of the subarray which has the maximum sum among all subarrays is maximized.
A subarray is a non-empty sequence of consecutive elements of the array.
The first line of the input contains an integer T (1 ≤ T ≤ 10) denoting the number of test cases. Then the description of the T test cases follows.
The first line of each of the test cases start with two integers N (1 ≤ N ≤ 5000) and K (0 ≤ K ≤ 5000). It is followed by a line having N integers, Ai (Ai ≤ 100000), denoting the array.
For every test case, in a separate line, output one integer which is the sum of the subarray which has the maximum sum among all subarrays that you can get after replacing at most K numbers with 0s.
Input | Output |
---|---|
2 5 3 1 2 3 4 5 7 2 1 -4 1 -10 -11 2 -6 | Case 1: 15 Case 2: 3 |
In the first test case we don't need to replace any number with 0.
In the second case we can replace -10 and -11 to get the following array: 1 -4 1 0 0 2 -6. The subarray [1 0 0 2] has the maximum sum which is equal to 3.