#6564. 连续最大值

连续最大值

Description

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

Input

第一行包含一个整数tt (1≤t≤600) — 测试用例的数量。
每个测试用例由两行组成。
每个测试用例的第一行包含两个整数nnkk (1≤k≤n≤100) — 数组的长度和上述语句中的数字。
第二行有nn个整数a1a_{1}a2a_{2},...,ana_{n}(i≤ana_{n}10910^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.

提示

第一个例子,我们可以通过选取a1a_{1}a2a_{2}得到1111分且不用进行任何操作
第三个例子,我们可以交换a1a_{1}a4a_{4}再选取a3a_{3}a4a_{4}a5a_{5}得到15分