C. Сделайте перестановку
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив целых чисел $$$a$$$ длины $$$n$$$. Вы можете выполнять два вида операций.

  • Удалить целое число из $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите минимальную стоимость, которую нужно потратить, чтобы сделать из массива перестановку.

Пример
Входные данные
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
Примечание

В первом наборе входных данных массив уже является перестановкой, поэтому операции не нужны.

Во втором наборе входных данных мы можем удалить числа $$$5$$$, $$$6$$$ и получить перестановку $$$[1,2,3]$$$. Стоимость таких операций будет равна $$$2$$$. Обратите внимание, что мы также можем получить перестановку, вставив число $$$4$$$, но это стоит $$$5$$$.

В третьем наборе входных данных мы можем просто удалить все числа, кроме первой $$$1$$$. Это стоит $$$8$$$, а окончательный массив $$$[1]$$$ представляет собой перестановку длины $$$1$$$.

В четвертом наборе входных данных мы можем удалить все числа, кроме $$$2$$$, и вставить одно число $$$1$$$ на первую позицию. Это стоит $$$4+10=14$$$, а окончательный массив $$$[1,2]$$$ представляет собой перестановку длины $$$2$$$.