#A1002P901. 摧毁

摧毁

题目描述

坐地日行八万里,巡天遥看一千河。 2077年,人类不仅仅是赛博科技得到了发展,太空技术也己经得到了极大的发展。地球的不同外轨道上已经充斥着各种功能用途的人造卫星。因为一个轨道上的卫星数量是有上限的,且卫星更新换代速度很快,如果想要发射新的卫星,需要把所有旧的卫星摧毁。人类有两种不同的武器可以摧毁卫星,具体如下(其中PW为新的能量单位)。 (1)使用定点激光武器花费1PW的代价摧毁任意轨道上指定的一个卫星。 (2)使用脉冲轨道武器花费cPW的代价把某一道上的所有卫星摧毁 现在有n个旧卫星分布在不同的外轨道上,你的任务是摧毁这些旧卫星。给出这n个卫星的轨道编号,求将这些卫星全部摧毁的最小代价是多少?

输入描述

第一行一个正整数 T ,表示测试数据组数。 接下来对于每组测试数据(注意:每组测试数据有 2 行数据,以下共 2*T 行数据): 第一行两个正整数 n 和 c 表示需要摧毁的卫星数量和使用脉冲轨道武器的代价。 第二行是 a1,a2,a3,...,ana_1,a_2,a_3,...,a_n 其中 aia_i 表示第i个卫星的轨道编号。

输出描述

输出T 行答案,对于每组测试数据,输出一行一个整数表示摧毁所有卫星的代价。

样例输入

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

样例说明

对于第一组测试数据,使用脉冲武器的代价为1 PW。轨道1 上有2 个卫星,轨道2 上有3 个卫星,轨道4 上有2 个卫星,轨道5 上有3 个卫星。因此对于轨道1、2、4、5,均使用脉冲武器各花费1PW 的代价可全部摧毁,总的代价为4 PW,很显然该方案为总代价最小方案。 对于第二组测试数据,使用脉冲武器的代价为2 PW。轨道1 上有1 个卫星,轨道2 上有3 个卫星,轨道3 上有1 个卫星。因此,对于轨道1 采用激光武器,轨道2 采用脉冲武器,轨道3 采用激光武器可全部摧毁所有卫星,总的代价为4 PW,很显然该方案使得总代价最小。

数据范围

对于 30%30\% 的数据, $T=1,1 \leq n \leq 10,1 \leq a_i \leq 10,1 \leq c \leq 10$; 对于 60%60\% 的数据, $1 \leq n \leq 10^3,1 \leq a_i \leq 1000,1 \leq c \leq 1000$ ; 对于 100%100\% 的数据, $1 \leq T \leq 10,1 \leq n \leq 10^6,1 \leq a_i \leq 10^6,1 \leq c \leq 100$ ,且所有测试数据的 nn 加起来不超过 10610^6