题目描述

四骑士潜入了一间存放贵重物品的金库。金库中有 $n$ 根金条，质量分别为 $a_1,a_2,\ldots,a_n$。

由于安保系统的存在，他们不能直接把所有金条拿走：离开时，如果留在金库中的金条数量小于从金库带走的金条数量，探测器就会触发。

不过，四骑士不愧是这一行的高手。他们决定连安保系统也一起骗过：在金库中，他们可以拿起任意一根金条，把它分成两根质量均为非零整数的新金条。分出来的金条也可以继续按照相同的方式分割。这样，金库中的金条总数会增加，他们就能带走更多黄金！

不幸的是，他们的潜入已经被发现。在被抓住之前，他们最多只能分割金条 $k$ 次。四骑士时间紧迫，又不愿错失黄金，所以需要尽快知道：他们最多能够从金库带走多少质量的黄金？

输入格式

每个测试包含多组数据。第一行包含一个整数 $t$，表示数据组数，满足 $1\le t\le 10^4$。接下来依次描述各组数据。

每组数据的第一行包含两个整数 $n,k$，分别表示金库中的金条数量，以及四骑士最多能够进行的分割次数，满足 $1\le n\le 2\cdot 10^5$、$1\le k\le 10^9$。

第二行包含 $n$ 个整数 $a_i$，其中第 $i$ 个数表示第 $i$ 根金条的质量，满足 $1\le a_i\le 10^9$。

保证所有数据组的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组数据，输出一个整数，表示四骑士最多能够带走的黄金质量。

4
4 7
6 10 5 1
3 1
12 8 12
1 4
5
5 7
1 4 2 7 15

19
24
4
26

3
7 2
481 145 877 391 359 141 647
5 2
794 251 19 838 600
4 100
12342284 102022008 124242424 173814882

2396
2232
412421594