#P1348. [CSP-X 山东 2022] 摧毁(destroy)
[CSP-X 山东 2022] 摧毁(destroy)
题目描述
坐地日行八万里,巡天遥看一千河。
2077年,人类不仅仅是赛博科技得到了发展,太空技术也已经得到了极大的发展。地球的不同外轨道上已经充斥着各种功能用途的人造卫星。因为一个轨道上的卫星数量是有上限的,且卫星更新换代速度很快,如果想要发射新的卫星,需要把所有旧的卫星摧毁。
人类有两种不同的武器可以摧毁卫星,具体如下(其中 PW 为新的能量单位):
- 使用定点激光武器花费 PW 的代价摧毁任意轨道上指定的一个卫星。
- 使用脉冲轨道武器花费 PW 的代价把某一轨道上的所有卫星摧毁。
现在有 个旧卫星分布在不同的外轨道上,你的任务是摧毁这些旧卫星。给出这 个卫星的轨道编号,求将这些卫星全部摧毁的最小代价是多少?
输入格式
第一行一个正整数 ,表示测试数据组数。
接下来对于每组测试数据(注意:每组测试数据有 行数据,以下共 行数据):
第一行两个正整数 和 表示需要摧毁的卫星数量和使用脉冲轨道武器的代价。
第二行是 ,其中 表示第 个卫星的轨道编号。
输出格式
输出 行答案,对于每组测试数据,输出一行一个整数表示摧毁所有卫星的代价。
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
提示
【样例说明】
对于第一组测试数据,使用脉冲武器的代价为 PW。轨道 上有 个卫星,轨道 上有 个卫星,轨道 上有 个卫星,轨道 上有 个卫星。因此对于轨道 、、、,均使用脉冲武器各花费 PW 的代价可全部摧毁,总的代价为 PW,很显然该方案为总代价最小方案。
对于第二组测试数据,使用脉冲武器的代价为 PW。轨道 上有 个卫星,轨道 上有 个卫星,轨道 上有 个卫星。因此,对于轨道 采用激光武器,轨道 采用脉冲武器,轨道 采用激光武器可全部摧毁所有卫星,总的代价为 PW,很显然该方案使得总代价最小。
【数据范围】
对于 的数据,;
对于 的数据,$T \le 100,1 \le n \le 10^3,1 \le a_i \le 1000,1 \le c \le 100$;
对于 的数据,$1 \le T \le 100,1 \le n \le 10^6,1 \le a_i \le 10^6,1 \le c \le 100$, 且所有测试数据的 加起来不超过 。