Problem E
Broken Calculator

You have a calculator, but unfortunately, it is broken. The (broken) calculator can maintain a variable $v$, which is initially $0$. There are only three things that it can do correctly (and, even then, it takes quite a bit of time):

• You can increment $v$; in other words, $v \gets v + 1$. This operation takes $A$ seconds.

• You can double the value of $v$; in other words, $v \gets v + v$. This operation takes $B$ seconds.

• You can reset the value of $v$ to $0$; in other words, $v \gets 0$. This operation takes $C$ seconds.

There is an urban legend that says that if you perform a magic ritual, you can fix the calculator. The ritual can be described as a list of $n$ integers $x_1, x_2, \ldots , x_ n$. It is triggered by having the calculator perform a sequence of operations, such that at some point in time while performing the operations, the value of $v$ is equal to $x_ i$ for all $1 \leq i \leq n$.

For example, if $x = \{ 1, 2, 3, 4, 6\} $, then the following sequence of operations will trigger the ritual:

• Increment $v$, so now $v = 1$. We have $v = x_1$.

• Double $v$, so now $v = 2$. We have $v = x_2$.

• Double $v$, so now $v = 4$. We have $v = x_4$.

• Reset $v$, so now $v = 0$.

• Increment $v$, so now $v = 1$.

• Increment $v$, so now $v = 2$.

• Increment $v$, so now $v = 3$. We have $v = x_3$.

• Double $v$, so now $v = 6$. We have $v = x_5$.

You know that the urban legend is (probably) not true, but it is quite an interesting problem to solve by itself. As an avid problem solver, you decided to find out the minimum time required to perform this ritual.

Unfortunately, $n$ is very large, thus you decided to code a program that solves this problem for you!

Input

The first line of input contains one integer $n$, the number of integers in the ritual ($1 \leq n \leq 400$).

The second line of input contains three integers $A$, $B$, and $C$, the time taken to perform the three operations, respectively ($1 \leq A, B, C \leq 10^{12}$).

The third line of input contains $n$ integers $x_1, x_2, \ldots , x_ n$, the integers in the ritual ($1 \leq x_1 < x_2 < \cdots < x_ n \leq 10^{18}$).

Output

Output a single integer denoting the minimum total time taken.

4
10 1 999999999999
4 5 6 7

42

5
3 1 1
1 2 3 4 6

14