题目描述

Crowdsource 正在为“图像标注”任务组织一场活动，共有 $N$ 个区域的参与者。每个区域的参与者数量分别为 $A_1, A_2, \ldots, A_N$。

在图像标注任务中，有 $M$ 个类别。Crowdsource 将参与者分配到这些类别中，分配方式需满足：一个区域的所有参与者必须被分配到同一个类别，并且每个类别至少分配到一个区域。该活动的成功度量值定义为每个类别中参与者数量的中位数之和。（提醒：一组整数的中位数是将这些整数从小到大排序后的“中间”数。当整数个数为偶数时，有两个“中间”数，此时中位数定义为这两个中间值的算术平均值（平均数）。）

例如，假设有 $N = 3$ 个区域，参与者数量分别为 $A_1 = 5$、$A_2 = 8$、$A_3 = 9$，我们要将它们分配到 $M = 2$ 个类别。如果将区域 $2$ 和 $3$ 分配到类别 $1$，区域 $1$ 分配到类别 $2$，则成功度量值为 $\operatorname{median}(\{A_2 = 8, A_3 = 9\}) + \operatorname{median}(\{A_1 = 5\}) = \frac{8+9}{2} + 5 = 8.5 + 5 = 13.5$。我们也可以将区域 $1$ 和 $2$ 分配到类别 $1$，区域 $3$ 分配到类别 $2$，此时成功度量值等于 $\{A_1 = 5, A_2 = 8\}$ 的中位数与 $\{A_3 = 9\}$ 的中位数之和，即 $\frac{5+8}{2} + 9 = 6.5 + 9 = 15.5$。

你的任务是找出通过将区域参与者分配到各个类别所能获得的最大可能成功度量值。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $M$：分别表示区域的数量和类别的数量。

下一行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最大可能的成功度量值。

如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

1
3 2
11 24 10

Case #1: 34.5

1
5 1
6 2 5 1 9

Case #1: 5.0

提示

在本测试中，将区域分配到类别共有 $6$ 种可能的方式：

• 将 $\{11, 24\}$ 分配到类别 $1$，$\{10\}$ 分配到类别 $2$，此时成功度量值为 $\frac{11+24}{2} + 10 = 17.5 + 10 = 27.5$。
• 将 $\{24, 10\}$ 分配到类别 $1$，$\{11\}$ 分配到类别 $2$，此时成功度量值为 $\frac{24+10}{2} + 11 = 17 + 11 = 28$。
• 将 $\{11, 10\}$ 分配到类别 $1$，$\{24\}$ 分配到类别 $2$，此时成功度量值为 $\frac{11+10}{2} + 24 = 10.5 + 24 = 34.5$。
• 其余 $3$ 种方式是将类别 $1$ 和 $2$ 的分配互换，这不会改变成功度量值。

因此，最大可能的成功度量值为 $34.5$。

限制条件

$1 \le T \le 100$。

$1 \le N \le 10^4$。

$1 \le M \le 10^4$。

$1 \le M \le N$。

对于所有 $i$，$1 \le A_i \le 10^5$。

测试集 1

$0 \le N - M \le 1$。

测试集 2

无额外限制。

翻译由 DeepSeek V4 Pro 完成