Maximum Sum of At Most K Contiguous Items

You are given a rack of items, each with an integer value. Your task is to determine the maximum possible sum that can be obtained from a contiguous sequence of items, with the constraint that the sequence contains at most \(k\) items.

Formally, given an array \(a_1, a_2, \dots, a_n\) and an integer \(k\), you need to find the maximum sum of a subarray \(a_i, a_{i+1}, \dots, a_j\) such that \(1 \leq (j-i+1) \leq k\). In other words, you are to maximize \(\displaystyle a_i + a_{i+1} + \cdots + a_j\) where \(j-i+1 \le k\).

Note: Since items may have negative values, if all numbers are negative, the answer is the maximum single element value.

inputFormat

The first line contains a single integer \(T\) representing the number of test cases.

Each test case consists of two lines:

• The first line contains two space-separated integers \(n\) and \(k\): the number of items in the rack and the maximum allowed length of the contiguous subarray, respectively.
• The second line contains \(n\) space-separated integers, representing the values of the items.

outputFormat

For each test case, output a single integer representing the maximum sum of values from a contiguous subarray of length at most \(k\). Each result should be printed on its own line.

## sample

1
7 3
10 -2 1 3 -1 2 5

10

</p>