Responsive image

问题 C: 小宇同学毁灭星球

问题 C: 小宇同学毁灭星球

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 78
[提交][状态][讨论版][命题人:]

题目描述

有一天,小宇同学想通过一个有 n 个行星的遥远系统建造一条新的超空间高速公路。第 i 个行星在 ai 轨道上,同一轨道上可能有多个行星。可惜所有星球都在路上,需要毁灭。

小宇同学有两台机器可以做到这一点。

一次操作中的第一台机器可以以 1  花费为代价摧毁任何行星。
一次操作中的第二台机器可以以 c 花费为代价摧毁该系统中单个轨道上的所有行星。
小宇同学可以根据需要多次使用每台机器。

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

输入描述

第一行包含单个整数 t (1≤t≤100) — 测试用例的数量。然后测试用例如下。

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

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

第二行包含 n 个整数 a1,a2,...,an (1≤ai≤100),其中 ai 是第 i 颗行星的轨道。

输出描述

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

样例输入

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

样例输出

4
4
2
2
[提交][状态]
ACM算法攻关部