题目描述

小 z 给定大家 $n$ 个数和一个数 $k$，要求对这 $n$ 个数进行 $k$ 次操作，每次操作取出两个数 $a_i$ 和 $a_j$，$(i≠j)$，将它们从数组中删除，之后将 $\frac{a_i}{a_j}$ 整除的值加进得分中。

$k$ 次操作后，将剩下的 $n−2*k$ 个数直接加入到得分中。

求最终得分的最小值。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n，k$（$1 \le n \le 100,0≤k≤[\frac{n}{2}]$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2e5$）——序列 $a$ 的元素。

输出格式

对于每个测试用例，在单独一行中输出求最终得分的最小值。

5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
2 0
4 2
9 2
1 10 10 1 10 2 7 10 3

2
16
0
6
16

提示

我们通过示例测试来理解题目。

在第一个测试用例中，一种获得分数2的方法如下：

1. 选择元素a₇=1和a₄=2进行操作，分数增加⌊1/2⌋=0，总分为0。数组变为 [1,1,1,1,3]；
2. [1,1,1,1,3] 接着选择元素a₁=1和a₅=3进行操作，分数增加⌊1/3⌋=0，总分为0。数组变为[1,1,1]；
3. 选择元素a₁=1和a₂=1进行操作，分数增加⌊1/1⌋=1，总分为1。数组变为[1]；
4. 将剩余元素1加到分数中，最终得分为2。

在第二个测试用例中，无论选择何种操作顺序，最终得分都是16。

在第三个测试用例中，一种获得分数0的方法如下：

1. 选择元素a₁=1和a₂=3进行操作，分数增加⌊1/3⌋=0，总分为0。数组变为[3,7]；
2. 选择元素a₁=3和a₂=7进行操作，分数增加⌊3/7⌋=0，总分为0。数组变为空；
3. 数组为空时分数不再变化。

在第四个测试用例中，无法进行任何操作，因此分数是数组元素之和：4 + 2 = 6。