A15452. Consecutive Sum

You are given an array $a$ with $n$ integers. You can perform the following operation at most $k$ times:

- Choose two indices $i$ and $j$ , in which $i \,\bmod\, k = j \,\bmod\, k$ ( $1 \le i < j \le n$ ).
- Swap $a_i$ and $a_j$ .

After performing all operations, you have to select $k$ consecutive elements, and the sum of the $k$ elements becomes your score. Find the maximum score you can get.

Here $x \bmod y$ denotes the remainder from dividing $x$ by $y$ .

The first line contains one integer $t$ ( $1 \le t \le 600$ ) — the number of test cases.

Each test case consists of two lines.

The first line of each test case contains two integers $n$ and $k$ ( $1 \le k \le n \le 100$ ) — the length of the array and the number in the statement above.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ) — the array itself.

For each test case, print the maximum score you can get, one per line.

In the first test case, we can get a score of $11$ if we select $a_1, a_2$ without performing any operations.

In the third test case, we can get a score of $15$ if we first swap $a_1$ with $a_4$ and then select $a_3, a_4, a_5$ .