CF2229F Load Unbalancing

请注意本题运行时间限制非常低。 给定一个长度为 $n$ 的序列 $a$，以及一个整数 $k$。 你可以先随意重新排序序列 $a$ 的元素。之后，定义 $f(a)$ 的过程如下： - 令 $b$ 为一个长度为 $k$ 的数组，初始值全部为零。 - 依次对于每一个 $1 \le i \le n$，将 $a_i$ 加到 $b$ 中的任意一个最小元素上。 - 完成上述过程后，$f(a) = \max(b)$。 请你求出在所有 $a$ 的排列方式中，$f(a)$ 的最大可能值。

每个测试点包含多个测试用例。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。接下来是各个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 18$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。 保证所有测试用例的 $2^n$ 之和不超过 $2^{18}$。

对于每个测试用例，输出一个整数，即所有排列方式下 $f(a)$ 能取得的最大值。

在第二个样例的第一个测试用例中，一种最优的 $a$ 排列方式为 $[1, 4, 2, 5]$。具体计算 $f(a)$ 的过程如下： | $i$ | $a_i$ | $b$| |:---:|:---:|:---:| |$ - $|$ - $|$ [0, 0] $| |$ 1 $|$ 1 $|$ [1, 0] $| |$ 2 $|$ 4 $|$ [1, 4] $| |$ 3 $|$ 2 $|$ [3, 4] $| |$ 4 $|$ 5 $|$ [8, 4] $| 此时 $f(a) = \max([8,4]) = 8$。可以证明最大 $f(a)$ 为 $8$。 在第二个样例的第三个测试用例中，一种最优的 $a$ 排列方式为 $[3, 1, 2, 3, 5, 4, 3, 4]$。 由 ChatGPT 5 翻译