hzCPPOJ

集合

时间限制:  2 s      内存限制:   128 MB
提交:21     正确:4     分值:99

题目描述

给定包含\( n \)个数的可重集合,你可以对它进行两种操作:

1.删除集合中的任意一个数字,这个操作需要花费\( c \)的代价

2.向集合中加入任意一个你指定的数字,这个操作需要花费\( d \)的代价

你可以进行任意次数的操作(包括0次)。假设最后你的集合中包含了\( m \)个数字,你需要满足\( m \neq 0 \),且集合中不重不漏的包含了\(1,2,3 \dots m \)这些数字。你希望最小化操作的代价之和,求这个代价。

输入

每个测试点包含多个测试用例。第一行包含一个整数 \( t \)(\( 1 \le t \le 10^4 \))--- 表示测试用例的数量。接下来是它们的描述。

每个测试用例的第一行包含三个整数 \( n \)、\( c \)、\( d \)(\( 1 \le n \le 10^5 \),\( 1 \le c,d \le 10^9 \))。

每个测试用例的第二行包含 \( n \) 个整数 \( a_{1}, a_{2}, \ldots, a_{n} \)(\( 1 \le a_{i} \le 10^9 \))。

保证所有测试用例的 \( n \) 的总和不超过 \( 2 \cdot 10^5 \)。

输出

对于每组数据,输出一行一个整数表示答案

样例

样例输入:
8 3 3 3 1 2 3 5 1 5 1 2 3 5 6 5 2 3 1 1 1 3 3 5 1 10 2 4 6 8 10 6 2 8 7 3 5 4 4 8 4 10 1 1 2 6 7 4 3 3 2 5 8 7 2 1000000000 1 1000000000 1
样例输出:
0 2 8 14 20 3 12 999999998

提示

令 \( M = \max a_{i} \)

对于 \( 30\% \)的数据,满足\( 1\le n,M \le 100 \)

对于 \( 50\% \)的数据,满足\( 1\le n,M \le 1000 \)

对于所有数据,满足\( 1\le \sum n \le 2\cdot 10^5 ,1\le n \le 10^5 , 1\le M \le 10^9 \)

提交人

GGyan