题目描述

给定一个长度为 $n$ 的序列 $a$ 和一个整数 $k$。你可以先任意重排序列 $a$。

之后定义 $f(a)$：

• 令长度为 $k$ 的数组 $b$ 初始全为 $0$；
• 按当前顺序依次处理 $a_i$；
• 每次把 $a_i$ 加到数组 $b$ 中的某个最小元素上；
• 处理结束后，$f(a)=\max(b)$。

求在所有重排中，$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)$ 的最大可能值。

样例 1

1
18 5
837492015 264819073 519603847 902746518 173058264 648291507 395174620 781532946 506847193 924613708 158397042 673029415 240785631 819456270 461302987 730619824 528947163 894271056

2823249283

样例 2

6
4 2
1 2 4 5
1 1
10
8 3
3 4 1 3 2 4 5 3
3 1
1000000000 1000000000 1000000000
17 6
6 7 67 4 1 41 6 9 69 3 1 4 1 5 9 2 6
2 2
1 2

8
10
11
3000000000
85
2

约束与提示

• 时间限制：1.5 秒

• 内存限制：256 MB

• 原题编号：CF2229F