codeforces#P1733A. Consecutive Sum
Consecutive Sum
Description
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.
Input
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.
Output
For each test case, print the maximum score you can get, one per line.
5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997
11
7
15
10
2999999997
Note
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$.