Planets

题意翻译

给你一个序列 $a$，你可以分别进行如下操作任意次： - 花费 $1$ 的代价删除 $a_i$。 - 花费 $c$ 的代价删除 $\forall a_i=x$，$x$自定。 求删除整个序列的最小代价。**多测**。

题目描述

One day, Vogons wanted to build a new hyperspace highway through a distant system with $ n $ planets. The $ i $ -th planet is on the orbit $ a_i $ , there could be multiple planets on the same orbit. It's a pity that all the planets are on the way and need to be destructed. Vogons have two machines to do that. - The first machine in one operation can destroy any planet at cost of $ 1 $ Triganic Pu. - The second machine in one operation can destroy all planets on a single orbit in this system at the cost of $ c $ Triganic Pus. Vogons can use each machine as many times as they want. Vogons are very greedy, so they want to destroy all planets with minimum amount of money spent. Can you help them to know the minimum cost of this project?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Then the test cases follow. Each test case consists of two lines. The first line contains two integers $ n $ and $ c $ ( $ 1 \le n, c \le 100 $ ) — the number of planets and the cost of the second machine usage. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 100 $ ), where $ a_i $ is the orbit of the $ i $ -th planet.

输出格式

For each test case print a single integer — the minimum cost of destroying all planets.

输入输出样例

输入样例 #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

说明

In the first test case, the cost of using both machines is the same, so you can always use the second one and destroy all planets in orbit $ 1 $ , all planets in orbit $ 2 $ , all planets in orbit $ 4 $ , all planets in orbit $ 5 $ . In the second test case, it is advantageous to use the second machine for $ 2 $ Triganic Pus to destroy all the planets in orbit $ 2 $ , then destroy the remaining two planets using the first machine. In the third test case, you can use the first machine twice or the second machine once. In the fourth test case, it is advantageous to use the first machine twice.

题目大意：
给定一个序列 $a$，可以通过以下两种操作任意次来删除序列中的元素：
- 花费1单位代价删除一个元素 $a_i$。
- 花费 $c$ 单位代价删除所有值为 $x$ 的元素，$x$ 可以自定。

求删除整个序列的最小代价。题目包含多组测试数据。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 $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上的所有行星是有利的，然后使用第一种机器摧毁剩下的两个行星。
- 在第三个测试案例中，可以使用第一种机器两次或第二种机器一次。
- 在第四个测试案例中，使用第一种机器两次是有利的。题目大意： 给定一个序列 $a$，可以通过以下两种操作任意次来删除序列中的元素： - 花费1单位代价删除一个元素 $a_i$。 - 花费 $c$ 单位代价删除所有值为 $x$ 的元素，$x$ 可以自定。 求删除整个序列的最小代价。题目包含多组测试数据。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $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上的所有行星是有利的，然后使用第一种机器摧毁剩下的两个行星。 - 在第三个测试案例中，可以使用第一种机器两次或第二种机器一次。 - 在第四个测试案例中，使用第一种机器两次是有利的。