CF2229F.Load Unbalancing

Note the unusually low time limit.

You are given a sequence $a$ of length $n$, as well as an integer $k$.

You may first reorder the elements of $a$ however you like. Then, define $f(a)$ as follows:

• Let $b$ be an array of length $k$ which is initially all zeros.
• For each $1 \le i \le n$ in order, add $a_i$ to any minimum element of $b$.
• At the end of this process, $f(a) = \max(b)$.

Find the maximum possible value of $f(a)$ among all rearrangements of $a$.

注意：本题的时间限制异常严格。

给定一个长度为 $n$ 的序列 $a$，以及一个整数 $k$。

你可以首先以任意方式重排序列 $a$ 的元素。然后，定义函数 $f(a)$ 如下：

• 令 $b$ 是一个长度为 $k$ 的数组，初始时所有元素均为 $0$。
• 按顺序对每个 $1 \le i \le n$，将 $a_i$ 加到 $b$ 中任意一个最小元素上。
• 此过程结束后，定义 $f(a) = \max(b)$。

求在 $a$ 的所有重排中，$f(a)$ 的最大可能值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 18$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $2^n$ over all test cases does not exceed $2^{18}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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}$。

For each test case, output a single integer — the maximum possible value of $f(a)$ among all rearrangements of $a$.

对于每个测试用例，输出一个整数——在数组 $a$ 的所有重排中，$f(a)$ 的最大可能值。

In the first test case of the second example, one optimal rearrangement of $a$ is $[1, 4, 2, 5]$. $f(a)$ is computed as follows:

$i$

$a_i$

$b$

$-$

$-$

$[0, 0]$

$1$

$1$

$[1, 0]$

$2$

$4$

$[1, 4]$

$3$

$2$

$[3, 4]$

$4$

$5$

$[8, 4]$

After this, $f(a) = \max([8,4]) = 8$. It can be shown that the maximum achievable $f(a)$ is $8$.

In the third test case of the second example, one optimal rearrangement of $a$ is $[3, 1, 2, 3, 5, 4, 3, 4]$.

在第二个示例的第一个测试用例中，数组 $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]$。