Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Subarray Sum

By bertho_coder · Limits 4s, 512 MB

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.

Input

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.

Output

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.

Samples

InputOutput
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.


Discussion
Submit

Login to submit