Bowling for Numbers

At a carnival, a popular game is Bowling for Numbers. A large number of bowling pins are lined up in a row. Each pin has a number printed on it, which is the score you earn for knocking that pin over. You are given several bowling balls; each ball is wide enough to knock over a few consecutive, adjacent pins.

For example, suppose the row of pins is:

2 8 5 1 9 6 9 3 2

If you are given two balls, each able to knock over three adjacent pins, the best score you can achieve is $39$: one throw knocks over $2 + 8 + 5 = 15$ and the other knocks over $9 + 6 + 9 = 24$. No two throws may overlap, because a pin that has already been knocked over cannot be knocked over again.

A greedy approach — repeatedly taking the throw worth the most among the pins still standing — often comes close, but it does not always reach the maximum. Your task is to compute the true maximum score.

Each ball knocks over a block of exactly $w$ consecutive pins from the original row, and no two balls may cover the same pin. You do not have to use every ball.

The input consists of several test cases.

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

Each test case begins with a line containing three integers $n$, $k$, and $w$:

• $n$ ($1 \le n \le 30000$) — the number of bowling pins;
• $k$ ($1 \le k \le 500$) — the number of balls available;
• $w$ ($1 \le w \le n$) — the width of each ball, i.e. the number of adjacent pins it knocks over.

The next $n$ lines each contain a single non-negative integer less than $10000$, giving the score of each pin, in order.

For each test case, output a single line containing the maximum score the player can achieve. This score is guaranteed to be less than one billion.