长度为 $$$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
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
输出 #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$$$。