CF1440B.Sum of Medians

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.

一个长度为 $n$ 的整数数组的中位数，是指将该数组元素按非递减顺序排列后，位于第 $\lceil {\frac{n}{2}} \rceil$（向上取整）个位置上的数。位置编号从 $1$ 开始。例如，数组 $[2, 6, 4, 1, 3, 5]$ 的中位数为 $3$。尽管中位数还有其他定义方式，但在本题中，我们始终采用上述定义。

给定两个整数 $n$ 和 $k$，以及一个长度为 $nk$ 的非递减整数数组。请将所有数字划分为 $k$ 个大小均为 $n$ 的数组，使得每个数字恰好属于其中一个数组。

你希望这 $k$ 个数组各自的中位数之和尽可能大。求这个可能的最大和。

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

第一行包含一个整数 $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$。

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

对于每个测试用例，输出一个整数——所有 $k$ 个数组的中位数之和的最大可能值。

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

第一个测试的所有测试用例中可能的数组划分示例如下：

测试用例 $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$。