← 返回题目列表

Codeforces · 1733/A

A. 连续总和

中文机器翻译题面 查看原题

给定一个数组 $$$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$$$ 的分数。