# 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

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

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.