A. Последовательная сумма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$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$$$)  — сам массив.

Выходные данные

Для каждого набора входных данных выведите максимальное количество баллов, которое вы можете получить, по одному в каждой строке.

Пример
Входные данные
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
Примечание

В первом примере мы можем получить счет $$$11$$$, если выберем $$$a_1, a_2$$$ без выполнения операций.

В третьем примере, если мы поменяем местами $$$a_1$$$ и $$$a_4$$$, а потом выберем $$$a_3, a_4, a_5$$$, то мы получим счет $$$15$$$.