B. Сумма медиан
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Медиана массива целых чисел длины $$$n$$$ это число, стоящее на позиции $$$\lceil {\frac{n}{2}} \rceil$$$ (округление вверх) среди его элементов, упорядоченных по неубыванию. Нумерация позиций начинается с $$$1$$$. Например, медиана массива $$$[2, 6, 4, 1, 3, 5]$$$ равна $$$3$$$. Существуют другие определения медианы, но в этой задаче мы будем использовать именно это определение.

Даны два целых числа $$$n$$$ и $$$k$$$ и неубывающий массив целых чисел длины $$$nk$$$. Разделите его элементы на $$$k$$$ массивов размера $$$n$$$, так что каждый элемент попадет в ровно один массив.

Вы хотите, чтобы сумма медиан всех $$$k$$$ массивов была максимально возможной. Найдите эту максимально возможную сумму.

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

В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Следующие $$$2t$$$ строк содержат описания наборов входных данных.

В первой строке описания каждого набора входных данных находится два целых числа $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 1000$$$).

Во второй строке описания каждого набора входных данных содержится $$$nk$$$ целых чисел $$$a_1, a_2, \ldots, a_{nk}$$$ ($$$0 \leq a_i \leq 10^9$$$) — данный массив. Гарантируется, что массив неубывающий: $$$a_1 \leq a_2 \leq \ldots \leq a_{nk}$$$.

Гарантируется, что сумма $$$nk$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите единственное целое число — максимально возможную сумму медиан всех $$$k$$$ массивов.

Пример
Входные данные
6
2 4
0 24 34 58 62 64 69 78
2 2
27 61 81 91
4 3
2 4 16 18 21 27 36 53 82 91 92 95
3 4
3 11 12 22 33 35 38 67 69 71 94 99
2 1
11 41
3 3
1 1 1 1 1 1 1 1 1
Выходные данные
165
108
145
234
11
3
Примечание

Примеры возможных разделений на массивы для всех наборов входных данных первого теста:

Набор входных данных $$$1$$$: $$$[0, 24], [34, 58], [62, 64], [69, 78]$$$. Медианы массивов $$$0, 34, 62, 69$$$. Их сумма равна $$$165$$$.

Набор входных данных $$$2$$$: $$$[27, 61], [81, 91]$$$. Медианы массивов $$$27, 81$$$. Их сумма равна $$$108$$$.

Набор входных данных $$$3$$$: $$$[2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27]$$$. Медианы массивов $$$91, 36, 18$$$. Их сумма равна $$$145$$$.

Набор входных данных $$$4$$$: $$$[3, 33, 35], [11, 94, 99], [12, 38, 67], [22, 69, 71]$$$. Медианы массивов $$$33, 94, 38, 69$$$. Их сумма равна $$$234$$$.

Набор входных данных $$$5$$$: $$$[11, 41]$$$. Медиана единственного массива $$$11$$$. Сумма единственной медианы равна $$$11$$$.

Набор входных данных $$$6$$$: $$$[1, 1, 1], [1, 1, 1], [1, 1, 1]$$$. Медианы массивов $$$1, 1, 1$$$. Их сумма равна $$$3$$$.