您有一个长度为 $$$n$$$ 的整数数组 $$$a$$$。您可以进行两种操作。
- 从 $$$a$$$ 中删除一个整数。此操作的成本为$$$c$$$。
- 将任意正整数 $$$x$$$ 插入到 $$$a$$$ 的任意位置(前面、后面或任意两个连续元素之间)。此操作的成本为$$$d$$$。
您希望使最终数组成为任意正长度的排列。请输出这样做的最低成本。请注意,您可以在操作过程中将数组清空,但最终数组必须至少包含一个整数。
长度 $$$n$$$ 的排列是一个由 $$$n$$$ 个从 $$$1$$$ 到 $$$n$$$ 的不同整数以任意顺序组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,在一行中输出使最终数组成为排列的最小成本。
示例
输入 #1
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
输出 #1
0 2 8 14 20 3 12 999999998
注意
在第一个测试用例中,数组已经是一个排列,因此不需要进行操作。
在第二个测试用例中,我们可以删除数字 $$$5$$$、$$$6$$$ 以获得成本 $$$2$$$ 的排列 $$$[1,2,3]$$$。请注意,我们还可以通过插入数字 $$$4$$$ 来获得排列,但它的成本为 $$$5$$$。
在第三个测试用例中,我们可以删除除第一个数字 $$$1$$$ 之外的所有数字。花费$$$8$$$,最终的数组是$$$[1]$$$,它是长度$$$1$$$的排列。
在第四个测试用例中,我们可以删除除$$$2$$$之外的所有数字,并在第一个位置插入一个数字$$$1$$$。花费$$$4+10=14$$$,最终的数组是$$$[1,2]$$$,它是长度$$$2$$$的排列。