It's Fantastic Friday, so Izuku Midoriya goes to the local anime trading card dealership to explore the latest releases. He is currently trying to collect the entire "Plus Ultra" card set of anime characters. Unfortunately for him, he does not know how many characters are in this set. He does, however, see that each character has a unique "quirk number."
He has brought his own collection containing $$$N$$$ cards, some of which may be duplicates. His goal is to collect one of each character in a contiguous run of quirk numbers starting at $$$1$$$. More formally, he would like to collect exactly one card each with quirk number $$$1, 2, 3, \ldots K$$$ for some positive integer $$$K$$$. He does not want any duplicates or any extra character cards whose quirk numbers are not part of the contiguous run: this would ruin the collection.
Midoriya cannot bring himself to simply throw a card away; however the card dealership will allow him to trade in any character card he owns for any other card of his choice for $$$A$$$ yen. Midoriya can also buy any character card of his choice outright for $$$B$$$ yen. (It's possible that $$$A \gt B$$$: the card dealer loves anime, but may not be great at economics.) The shop has an unlimited supply of cards of every quirk number. In order to satisfy his wish of possessing a contiguous run of quirk numbers, what is the minimum amount of money Izuku Midoriya needs to spend?
The first line contains three space-separated integers $$$N$$$, $$$A$$$, and $$$B$$$ $$$(1 \leq N, A, B \leq 10^5)$$$.
The second line contains $$$N$$$ space-separated integers $$$c_i$$$ $$$(1 \leq c_i \leq 10^6)$$$, the quirk numbers of the cards that Midoriya already owns. Note that this list could contain duplicate quirk numbers.
Print a single integer: the minimum amount of yen Izuku Midoriya needs to pay so that the quirk numbers in his collection form a contiguous run $$$1, 2, \ldots, K$$$ for some $$$K$$$.
5 3 5 1 7 5 10 5
9
4 100 5 1 7 5 10
30
4 100 5 1 7 5 1000
115
In the first test case, he can trade in the card with quirk number $$$7$$$ for a new card with quirk number $$$2$$$; similarly he can trade $$$5$$$ for $$$3$$$ and $$$10$$$ for $$$4$$$. In this way he will have cards with quirk numbers $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, and $$$5$$$. These trades cost him $$$3*3 = 9$$$ yen.
In the second test case, he can buy all of the cards with quirk numbers $$$1$$$–$$$10$$$, excluding $$$1$$$, $$$5$$$, $$$7$$$, and $$$10$$$ which he already owns. This costs him $$$6*5 = 30$$$ yen.
In the third test case, he can trade in the card with quirk number $$$1000$$$ for quirk number $$$6$$$ and then buy the characters with quirk numbers $$$2$$$, $$$3$$$, and $$$4$$$. This costs him a total of $$$100+5*3 = 115$$$ yen.
