题目描述
小美有一个长度为 n 的数组 a1,a2,…,an , 他可以对数组进行如下操作:
- 删除第一个元素 a1 , 同时数组的长度减 1,花费为 x 。
- 删除整个数组,花费为 k×MEX(a) (其中 MEX(a) 表示 a 中未出现过的最小非负整数。例如 [0,1,2,4] 的 MEX 为 3 )。
小美想知道将 a 数组全部清空的最小代价是多少, 请你帮帮他吧.
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤1000) 代表数据组数, 每组测试数据描述如下:
第一行输入三个正整数 n,k,x (1≤n≤2×105,1≤k,x≤109) 代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。
a除此之外, 保证所有的 n 之和不超过 2×105 。
输出描述
对于每一组测试数据, 在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。
样例输入输出
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 ;