题目描述

给定一个长度为 $n$ 的整数数组 $a$。你最多可以进行 $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$），表示数组本身。

输出格式

对于每个测试用例，输出你能获得的最大得分，每行一个结果。

说明/提示

在第一个测试用例中，如果不进行任何操作，选择 $a_1, a_2$ 可以获得得分 $11$。

在第三个测试用例中，如果先交换 $a_1$ 和 $a_4$，然后选择 $a_3, a_4, a_5$，可以获得得分 $15$。

由 ChatGPT 4.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

11
7
15
10
2999999997