Maximum Total Energy Harvested

You are given a sequence of N stones arranged in a line. Each stone has a power value p_i. Starting from the first stone, you move forward through the stones and collect energy. At each stone i, you add its power to the accumulated total. However, you have a special rule: if you are at stone i and i > D (with D being a given non-negative integer), you are allowed to restart your accumulation by skipping some stones. Formally, define a dynamic programming state dp[i] as the maximum total energy collected when reaching stone i. The recurrence is:

$$ dp[i] = \max\bigl(dp[i-1] + p_i,\; p_i + \begin{cases} dp[i-D-1] & \text{if } i-D-1 \ge 0 \\ 0 & \text{otherwise} \end{cases}\bigr) $$

Your goal is to compute the maximum total energy that can be collected by the time you reach the last stone (stone number N).

Note: All power values are positive, so accumulating contiguous stones always increases the total energy. However, the possibility to restart the accumulation when skipping more than D stones is provided to handle the generalized scenario.

inputFormat

The first line contains a single integer T representing the number of test cases. Each test case is described as follows:

• The first line of each test case contains two space-separated integers N and D, where N is the number of stones and D is the maximum distance allowed for transferring energy.
• The second line contains N space-separated integers representing the power values of the stones.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line – the maximum total energy that can be collected upon reaching the last stone. Output is written to standard output (stdout).

## sample

2
5 2
1 2 3 4 5
3 1
10 20 30

15
60

</p>