Sum of Medians
Contest: Codeforces Round 684 (Div. 2)
Difficulty rating: 900
Tags: greedy, math

A median of an array of integers of length $$$n$$$ is the number standing on the $$$\lceil {\frac{n}{2}} \rceil$$$ (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting with $$$1$$$. For example, a median of the array $$$[2, 6, 4, 1, 3, 5]$$$ is equal to $$$3$$$. There exist some other definitions of the median, but in this problem, we will use the described one.

Given two integers $$$n$$$ and $$$k$$$ and non-decreasing array of $$$nk$$$ integers. Divide all numbers into $$$k$$$ arrays of size $$$n$$$, such that each number belongs to exactly one array.

You want the sum of medians of all $$$k$$$ arrays to be the maximum possible. Find this maximum possible sum.

Input format:
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 format:
For each test case print a single integer — the maximum possible sum of medians of all $$$k$$$ arrays.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

Example 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

Example output:
165
108
145
234
11
3

Editorial:
We will consider a greedy approach. We take the $$$\lceil {\frac{n}{2}} \rceil$$$ biggest numbers from the end of the array and the $$$\lfloor {\frac{n}{2}} \rfloor$$$ smallest numbers from the beginning. We take these elements as one group, erase them from our array and then continue the same procedure on the remaining array. This can be done in a loop of $$$O(k)$$$, by taking every $$$\lceil {\frac{n}{2}} \rceil$$$th character. We can also prove this claim. Imagine we have marked $$$k$$$ elements to be the medians of these arrays. Each one of these elements need at least $$$\lceil {\frac{n}{2}} \rceil - 1$$$ elements bigger than them and at least $$$\lfloor {\frac{n}{2}} \rfloor$$$ elements smaller than them to form a group in which it they are the median. So we can always push the biggest of these $$$k$$$ numbers forward until we have exactly $$$\lceil {\frac{n}{2}} \rceil - 1$$$ elements bigger than them, and by pushing forward the sum of medians either doesn't change or gets larger. So our algorithm will always give the biggest possible answer.
Time complexity: $$$O(nk)$$$ for each testcase