题目描述

小美有一个长度为n的数组 a1, a2, .... , an ，他可以对数组进行如下操作：

● 删除第一个元素a1，同时数组的长度减一，花费为x。

● 删除整个数组，花费为 k * MEX(a) （其中MEX(a) 表示a中未出现过的最小非负整数。例如[0,1,2,4]的 MEX为3 ）。

小美想知道将a数组全部清空的最小代价是多少，请你帮帮他吧。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1 <= T <= 1000) 代表数据组数，每组测试数据描述如下：

第一行输入三个正整数 n, k, x(1 <= n <= 2 * 10^5, 1 <= k, x <= 10^9) 代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。

第二行输入n个整数a1, a2, .... , an(0 <= ai <= n)，表示数组元素。

除此之外，保证所有的n之和不超过 2 * 10^5。

输出描述

对于每一组测试数据，在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。

输入示例

1
6 3 3
4 5 2 3 1 0

输出示例

15

提示信息

若不执行操作一就全部删除，MEX{4,5,2,3,1,0} = 6，花费 18；

若执行一次操作一后全部删除，MEX{5,2,3,1,0} = 4，花费 3+12；

若执行两次操作一后全部删除，MEX{2,3,1,0} = 4，花费 6+12；

若执行三次操作一后全部删除，MEX{3,1,0} = 2，花费 9+6；

若执行四次操作一后全部删除，MEX{1,0} = 2，花费 12+6；

若执行五次操作一后全部删除，MEX{0} = 1，花费 15+3；

若执行六次操作一，MEX{} = 0，花费 18；

时间限制：c/c++：1s；java：5s；其他语言：3s。