← 返回题目列表

Codeforces · 1730/A

A. 行星

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

有一天,沃贡斯想要通过一个拥有 $$$n$$$ 行星的遥远系统建造一条新的超空间高速公路。第 $$$i$$$ 行星位于 $$$a_i$$$ 轨道上,同一轨道上可能有多个行星。可惜所有的星球都在路上,需要毁灭。

Vogons 有两台机器可以做到这一点。

- 一次操作中的第一台机器可以摧毁任何行星,成本为 $$$1$$$ Triganic Pu。
- 一次操作中的第二台机器可以摧毁该系统中单个轨道上的所有行星,代价是 $$$c$$$ Triganic Pus。

沃贡人可以根据需要多次使用每台机器。

沃贡人非常贪婪,所以他们想用最少的钱摧毁所有的星球。你能帮助他们了解这个项目的最低成本吗?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是测试用例。

每个测试用例由两行组成。

第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$1 \le n, c \le 100$$$) — 行星数量和第二台机器使用的成本。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 行星的轨道。

输出

对于每个测试用例,打印一个整数 - 摧毁所有行星的最低成本。

示例

输入 #1

4
10 1
2 1 4 5 2 4 5 5 1 2
5 2
3 2 1 2 2
2 2
1 1
2 2
1 2

输出 #1

4
4
2
2

输入 #2

1
1 100
1

输出 #2

1

注意

在第一个测试用例中,使用两台机器的成本是相同的,因此您始终可以使用第二台机器并摧毁轨道上的所有行星 $$$1$$$、轨道上的所有行星 $$$2$$$、轨道上的所有行星 $$$4$$$、轨道上的所有行星 $$$5$$$。

在第二个测试用例中,使用第二台机器进行 $$$2$$$ Triganic Pus 摧毁 $$$2$$$ 轨道上的所有行星,然后使用第一台机器摧毁剩余的两颗行星是有利的。

在第三个测试用例中,您可以使用第一台机器两次或第二台机器一次。

在第四个测试用例中,使用第一台机器两次是有利的。