Trout III

Hint: This problem isn't actually related to the previous Trout tasks.

Following the successful disruption of the Newfound Zealous Irradiating Corporation's (NZIC) fishing ventures, the trout population was certainly affected. The trout have now set their sights upon building a network of spies to support their future ambitions. The trout have constructed a very long underground canal to facilitate their spy operations. There are $N$ spies, the $i$-th of which is located $P_i$ metres from the start of the canal.

Agent T has been tasked with getting a secret message to each of the spies. Agent T starts swimming from the beginning of the canal, with a single copy of the secret message, and swims along the canal. Due to strong currents, Agent T cannot swim backwards along the canal. At any point, they can stop to make copies of the message. Since Agent T will be swimming very fast, it will take them $A$ seconds to stop, and then $B$ seconds afterwards to make each copy. Furthermore, the messages are rather heavy so if Agent T is currently carrying $x$ messages, then it will take them $x$ seconds to swim the next metre.

Agent T can expertly throw the messages when swimming past a spy, so they do not need to stop to deliver a message. Note that at any point until Agent T has delivered the message to all spies, he must have at least one copy of the message on him, otherwise he cannot make any more copies.

Agent T has tasked you with creating a program to help figure out the shortest possible time to deliver the message to all the spies.

Input

The first line of input contains three space separated integers $N$, $A$, and $B$.

The second line of input contains $N$ space separated integers $P_1, \dots, P_N$.

Output

Output a single integer, the minimum number of minutes it will take to deliver the message to all the spies.

Constraints

• $2 \le N \le 100,000$
• $0 \le A, B \le 10^{10}$
• $1 \le P_i \le 10^9$
• The positions are given in ascending order.

Subtasks

• Subtask 1 (+9%): $A = 0$
• Subtask 2 (+19%): $N \le 100$
• Subtask 3 (+25%): $N \le 10,000$
• Subtask 4 (+18%): There exists an optimal solution where Agent T stops to create copies at most twice.
• Subtask 5 (+14%): The positions are equally spaced apart from each other and the beginning of the tunnel. That is, there exists some integer $X$ such that $P_i = X \times i$ for all $i$.
• Subtask 6 (+15%): No further constraints.

Notes

If you are using a type sensitive language like C++, Java, or C then make sure to use a 64 bit integer type to avoid integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.

If you are using Python and your solution is exceeding the time limit, try selecting Python 3.11 (PyPy 7.3.19) when submitting as this will generally make your code run faster.

Sample Explanations

Sample 1

There are four spy trout in the stream that need to receive a message. They are located 7, 29, 59, and 83 metres from the start of the canal respectively.

Agent T can deliver a message to all the trout in 173 seconds as follows:

• They start at the start of the canal, carrying one copy of the message. Agent T swims 7 metres downstream, taking $1 \times 7 = 7$ seconds, reaching the first spy.
• At this point Agent T stops, which takes 17 seconds. They then make one extra copy of the message. This takes them 13 seconds. They now carry two copies of the message.
• They give one copy to the first spy.
• They repeat this process, swimming to the second spy, making a copy, handing a copy to the second spy, swimming to the third spy, making a copy, handing a copy to the third spy.
• Finally, they swim to the last spy, this takes them 24 seconds. Then, they hand their only copy of the message to the last spy.

Sample 2

There are five spy trout in the stream that need to receive a message. They are located 13, 19, 23 72, and 84 metres from the start of the canal.

One possible non-optimal way to deliver the messages is as follows:

• Swim to spy 1. This takes $1 \times 13 = 13$ seconds.
• Make four copies of the message. This takes $34 + 2 \times 4 = 42$ seconds.
• Hand spy 1 a copy of the message.
• Swim to spy 2. This takes $4 \times 6 = 24$ seconds as Agent T is carrying four copies of the message.
• Hand spy 2 a copy of the message.
• Swim to spy 3. This takes $3 \times 4 = 12$ seconds.
• Hand spy 3 a copy of the message.
• Swim to spy 4. This takes $2 \times 49 = 98$ seconds.
• Hand them a copy of the message.
• Swim to spy 5. This takes $1 \times 12 = 12$ seconds.
• Hand them a copy of the message.