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 $ .

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} $ .

For each test case, output a single integer — the maximum possible value of $ f(a) $ among all rearrangements of $ 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] $ .