Sum of Medians

Description:

Input:

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The next $$$2t$$$ lines contain descriptions of test cases.

The first line of the description of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 1000$$$).

The second line of the description of each test case contains $$$nk$$$ integers $$$a_1, a_2, \ldots, a_{nk}$$$ ($$$0 \leq a_i \leq 10^9$$$) — given array. It is guaranteed that the array is non-decreasing: $$$a_1 \leq a_2 \leq \ldots \leq a_{nk}$$$.

It is guaranteed that the sum of $$$nk$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output:

For each test case print a single integer — the maximum possible sum of medians of all $$$k$$$ arrays.

Sample Input:

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

Sample Output:

165
108
145
234
11
3

Note:

The examples of possible divisions into arrays for all test cases of the first test:

Test case $$$1$$$: $$$[0, 24], [34, 58], [62, 64], [69, 78]$$$. The medians are $$$0, 34, 62, 69$$$. Their sum is $$$165$$$.

Test case $$$2$$$: $$$[27, 61], [81, 91]$$$. The medians are $$$27, 81$$$. Their sum is $$$108$$$.

Test case $$$3$$$: $$$[2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27]$$$. The medians are $$$91, 36, 18$$$. Their sum is $$$145$$$.

Test case $$$4$$$: $$$[3, 33, 35], [11, 94, 99], [12, 38, 67], [22, 69, 71]$$$. The medians are $$$33, 94, 38, 69$$$. Their sum is $$$234$$$.

Test case $$$5$$$: $$$[11, 41]$$$. The median is $$$11$$$. The sum of the only median is $$$11$$$.

Test case $$$6$$$: $$$[1, 1, 1], [1, 1, 1], [1, 1, 1]$$$. The medians are $$$1, 1, 1$$$. Their sum is $$$3$$$.