Maximum Coin Collection

Bob is navigating through a series of consecutive sections. Each section may either be empty, contain a certain number of coins, or hold an obstacle. Bob begins at section 1 and must reach section N while collecting as many coins as possible.

Some sections contain a coin value (denoted by a positive integer between 1 and 100) or 0 if empty; however, a section value of -1 means it contains an obstacle and cannot be entered. In addition, Bob has a limited number of jumps available. A jump allows him to skip exactly one section. Formally, if Bob is at section i having used j jumps, he can either:

• Move to section i+1 (provided that section does not have an obstacle), accumulating the coins therein.
• If he still has jumps remaining (i.e. j < J), he can jump to section i+2 (again, only if that section is accessible), using up one jump.

The task is to compute the maximum number of coins Bob can collect by the time he reaches section N. The underlying dynamic programming state can be defined as:

$$dp[i+1][j]=\max(dp[i+1][j],\; dp[i][j]+a_{i+1})$$

and if a jump is used (with the condition that \(j < J\)):

$$dp[i+2][j+1]=\max(dp[i+2][j+1],\; dp[i][j]+a_{i+2})$$

where \(a_i\) represents the coin value at section \(i\) (or -1 if it is an obstacle). If Bob starts on an obstacle, he collects no coins but proceeds with the journey.

inputFormat

The input begins with a single integer T representing the number of test cases. For each test case, the first line contains two integers N and J (the number of sections and the maximum number of jumps allowed, respectively). The following line contains N space-separated integers. Each integer can be:

• A non-negative coin value (0 or a positive integer up to 100), or
• -1, representing an obstacle.

outputFormat

For each test case, output a single integer on a new line — the maximum number of coins Bob can collect by reaching section N.

## sample

3
5 1
0 10 -1 5 0
5 2
0 0 0 50 10
4 0
0 -1 20 0

15
60
0

</p>