You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给出一个数组$a$有$n$个整数，你可以进行最多$k$次操作：
1.选择两个数组下标i和j，且满足 $i \bmod k$= $j \bmod k$(1≤i<j≤n) 2.交换$a_{i}$和$a_{j}$（两步为一次操作）
执行所有操作后，你必须选择$k$个连续元素，以及$k$个元素成为您的分数。找到你可以获得的最高分。

Input

第一行包含一个整数$t$ (1≤t≤600） — 测试用例的数量。
每个测试用例由两行组成。
每个测试用例的第一行包含两个整数$n$和$k$ (1≤k≤n≤100） — 数组的长度和上述语句中的数字。
第二行有$n$个整数$a_{1}$，$a_{2}$，...,$a_{n}$(i≤$a_{n}$≤$10^9$)

Output

对于每个测试用例，打印您可以获得的最高分数，每行一个。

Samples

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

Limitation

1s, 1024KiB for each test case.

提示

第一个例子，我们可以通过选取$a_{1}$，$a_{2}$得到$11$分且不用进行任何操作
第三个例子，我们可以交换$a_{1}$和$a_{4}$再选取$a_{3}$，$a_{4}$，$a_{5}$得到15分