B. Card Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing a card game with $$$n$$$ cards, with each card having a value positive or negative. You need to choose a non - empty subsequence of cards such that the total value of the cards is maximum.

Now your evaluator likes the number k so much. He will only like your sequence if you can divide the number of cards into groups of k. Hence you need to choose such a subsequence of cards which he likes.

A subsequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several(possibly zero) elements.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of testcases

  • The first line contains two integers, $$$n$$$ ($$$1 \le n \le 1000$$$), and $$$k$$$ ($$$1 \le k \le 1000$$$), where $$$n$$$ is the number of cards and $$$k$$$ is your evaluators favourite number
  • The second line contains $$$n$$$ integers, $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$), the values of the cards
Output

For each test, print the best value you can achieve

Example
Input
4
2 1
1 2
5 4
-1 -2 -3 -4 -5
6 2
4 -5 6 -3 4 -6
1 1
0
Output
3
-10
11
0