D. Serval and Kaitenzushi Buffet
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Serval has just found a Kaitenzushi buffet restaurant. Kaitenzushi means that there is a conveyor belt in the restaurant, delivering plates of sushi in front of the customer, Serval.

In this restaurant, each plate contains exactly $$$k$$$ pieces of sushi and the $$$i$$$-th plate has a deliciousness $$$d_i$$$. Serval will have a meal in this restaurant for $$$n$$$ minutes, and within the $$$n$$$ minutes, he must eat up all the pieces of sushi he took from the belt.

Denote the counter for uneaten taken pieces of sushi as $$$r$$$. Initially, $$$r=0$$$. In the $$$i$$$-th minute ($$$1\leq i\leq n$$$), only the $$$i$$$-th plate of sushi will be delivered in front of Serval, and he can do one of the following:

  • Take the $$$i$$$-th plate of sushi (whose deliciousness is $$$d_i$$$) from the belt, and $$$r$$$ will be increased by $$$k$$$;
  • Eat one uneaten piece of sushi that he took from the belt before, and $$$r$$$ will be decreased by $$$1$$$. Note that you can do this only if $$$r \gt 0$$$;
  • Or, do nothing, and $$$r$$$ will remain unchanged.

Note that after the $$$n$$$ minutes, the value of $$$r$$$ must be $$$0$$$.

Serval wants to maximize the sum of the deliciousnesses of all the plates he took. Help him find it out!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq k \lt n\leq 2\cdot 10^5$$$) — the number of minutes of the meal and the number of sushi pieces in each plate.

The second line contains $$$n$$$ integers $$$d_1, d_2, \ldots, d_n$$$ ($$$1\leq d_i\leq 10^9$$$) — the deliciousness of each plate.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print a single integer — the maximum possible sum of the deliciousnesses of all the plates Serval took.

Example
Input
5
5 2
3 6 4 1 2
7 1
3 1 4 1 5 9 2
4 3
4 3 2 1
6 2
1 3 5 2 4 6
6 1
1000000000 1 1000000000 1 1000000000 1
Output
6
16
4
6
3000000000
Note

In the first test case, it can be shown that Serval can eat up at most one plate of sushi. Since the second plate of sushi has the greatest deliciousness $$$6$$$ among all the plates, he will take it from the belt in the second minute, and then eat it up in the following $$$2$$$ minutes.

Minute$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$
Action — TakeEatEat — 
$$$r$$$ after action$$$0$$$$$$2$$$$$$1$$$$$$0$$$$$$0$$$
Deliciousnesses gained$$$0$$$$$$6$$$$$$6$$$$$$6$$$$$$6$$$

In the second test case, it can be shown that it is optimal for Serval to eat up the first, third, and sixth plates of sushi. The sum of the deliciousnesses of these plates is $$$3 + 4 + 9 = 16$$$.

Minute$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$
ActionTakeEatTakeEat — TakeEat
$$$r$$$ after action$$$1$$$$$$0$$$$$$1$$$$$$0$$$$$$0$$$$$$1$$$$$$0$$$
Deliciousnesses gained$$$3$$$$$$3$$$$$$7$$$$$$7$$$$$$7$$$$$$16$$$$$$16$$$