Bowling for Numbers++

You are playing a game called Bowling for Numbers. A row of $n$ bowling pins stands in a line. The $i$-th pin has an integer score $a_i$ printed on it — the points you gain by knocking that pin over. Some pins are penalty pins whose score is negative, so knocking one over lowers your total.

You are given $k$ bowling balls. Each ball is wide enough to knock over up to $w$ consecutive pins: a single throw covers a window of $w$ adjacent positions and knocks over every pin still standing inside that window. A pin's score is counted at most once, no matter how many balls pass over it.

A throw's window may extend past the left or right end of the row (everything beyond the ends is empty space), and it may pass through gaps left by pins that earlier throws already knocked down. You can exploit this: by aiming a throw so that some of its $w$ positions land on empty space — off an end of the row, or on positions a previous throw already cleared — you can knock over fewer than $w$ pins and skip over penalty pins. A ball may even be thrown so that it knocks over nothing.

Throw your $k$ balls to maximize the total score of the knocked-over pins. You do not have to use every ball.

Equivalently: the pins you knock over are exactly those whose position is covered by at least one of your (at most $k$) length-$w$ windows, and your score is the sum of $a_i$ over every covered position. Report the maximum score you can achieve.

The first line contains an integer $t$ ($1 \le t \le 10$) — the number of test cases. The test cases follow.

The first line of each test case contains three integers $n$, $k$, and $w$:

• $n$ ($1 \le n \le 10000$) — the number of pins;
• $k$ ($1 \le k \le 500$) — the number of balls;
• $w$ ($1 \le w \le 100$) — the width of a ball, i.e. how many consecutive pins one throw can knock over.

Each of the next $n$ lines contains one integer — the scores of the pins from left to right. Every score satisfies $-10000 \le a_i \le 10000$.

For each test case, print a single line containing the maximum total score that can be achieved. The answer is guaranteed to be less than one billion.