← 返回题目列表

Codeforces · 2022/B

B. 卡尔推销员

中文机器翻译题面 查看原题

卡雷尔是一家汽车经销店的推销员。经销商有 $$$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$$$) - 不同型号汽车的数量以及 Karel 可以说服客户购买的最大汽车数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 每个型号的汽车数量。

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

输出

对于每个测试用例,输出销售所有汽车所需的最小可能客户数量。

示例

输入 #1

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

输出 #1

3
3
9
7

注意

对于第一种情况,Karel 只需要吸引 $$$3$$$ 客户。他将说服顾客购买以下型号的汽车:

- 客户 $$$1$$$ 购买型号为 $$$1$$$ 和 $$$3$$$ 的 $$$2$$$ 汽车。
- 客户 $$$2$$$ 购买型号为 $$$1$$$ 和 $$$2$$$ 的 $$$2$$$ 汽车。
- 客户 $$$3$$$ 购买型号为 $$$1$$$ 和 $$$3$$$ 的 $$$2$$$ 汽车。

对于第二种情况,Karel 只需要吸引 $$$3$$$ 客户。他将说服顾客购买以下型号的汽车:

- 客户 $$$1$$$ 购买型号为 $$$1$$$ 和 $$$3$$$ 的 $$$2$$$ 汽车。
- 客户 $$$2$$$ 购买型号为 $$$1$$$、$$$2$$$ 和 $$$3$$$ 的 $$$3$$$ 汽车。
- 客户 $$$3$$$ 购买了 $$$1$$$ 汽车,型号为 $$$3$$$。