B. 汽车销售员卡尔

时间限制：每个测试 $1$ 秒
内存限制：$256$ MB

卡尔是一家汽车经销店的销售员。该经销店有 $n$ 种不同型号的汽车。第 $i$ 种型号有 $a_i$ 辆车。卡尔是一位出色的销售人员，他可以说服顾客购买最多 $x$ 辆汽车（由卡尔选择），只要这些汽车来自不同的型号。

确定卡尔需要吸引的最少顾客数量，以便卖出所有汽车。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 5 \cdot 10^5$，$1 \le x \le 10$），分别表示不同汽车型号的数量以及卡尔可以说服每个顾客购买的最多汽车数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每种型号的汽车数量。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出卖出所有汽车所需的最少顾客数量。

示例

输入

4
3 2
3 1 2
3 3
2 1 3
5 3
2 2 1 9 2
7 4
2 5 3 3 5 2 5

输出

3
3
9
7

样例解释

对于第一个测试用例，卡尔只需要吸引 $3$ 个顾客。他说服顾客购买以下型号的汽车：

• 顾客 $1$ 购买 $2$ 辆车，型号为 $1$ 和 $3$。
• 顾客 $2$ 购买 $2$ 辆车，型号为 $1$ 和 $2$。
• 顾客 $3$ 购买 $2$ 辆车，型号为 $1$ 和 $3$。

对于第二个测试用例，卡尔只需要吸引 $3$ 个顾客。他说服顾客购买以下型号的汽车：

• 顾客 $1$ 购买 $2$ 辆车，型号为 $1$ 和 $3$。
• 顾客 $2$ 购买 $3$ 辆车，型号为 $1$、$2$ 和 $3$。
• 顾客 $3$ 购买 $1$ 辆车，型号为 $3$。