给定一个数组 $$$a$$$,其中包含 $$$n$$$ 整数。您最多可以执行 $$$k$$$ 次以下操作:
- 选择两个索引 $$$i$$$ 和 $$$j$$$,其中 $$$i \,\bmod\, k = j \,\bmod\, k$$$ ($$$1 \le i < j \le n$$$)。
- 交换 $$$a_i$$$ 和 $$$a_j$$$。
执行完所有操作后,您必须选择 $$$k$$$ 个连续元素,$$$k$$$ 元素的总和就是您的分数。找出你能得到的最高分。
这里 $$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 所得的余数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 600$$$) — 测试用例的数量。
每个测试用例由两行组成。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 100$$$) - 数组的长度和上面语句中的数字。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组本身。
输出
对于每个测试用例,打印您可以获得的最高分数,每行一个。
示例
输入 #1
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
输出 #1
11 7 15 10 2999999997
注意
在第一个测试用例中,如果我们选择$$$a_1, a_2$$$而不执行任何操作,我们可以得到$$$11$$$的分数。
在第三个测试用例中,如果我们首先将 $$$a_1$$$ 与 $$$a_4$$$ 交换,然后选择 $$$a_3, a_4, a_5$$$,我们可以获得 $$$15$$$ 的分数。