题目描述

一个长度为 $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$ 个数组的中位数之和的最大可能值。

说明/提示

以下是第一个测试样例所有测试用例的可能划分示例：

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

由 ChatGPT 4.1 翻译

样例

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