Apprentice magical girl Chiaro is taking a wizardry exam. The great wizard Shiro has placed $n$ magic orbs with no magic power in front of her. Chiaro needs to perform several spells to make these magic orbs reach specified magic power levels.

Specifically, initially, the magic power of all these orbs is 0. Chiaro needs to perform several spells so that the $i$-th magic orb eventually has a magic power of $a_i$. However, as an apprentice, Chiaro has limited knowledge of magic. She only knows two types of spells, and each spell consumes a certain amount of stamina:

• Increase the magic power of any single magic orb by 1, which consumes $x$ stamina.
• Choose any interval $[l, r]$ and double the magic power of all magic orbs from the $l$-th to the $r$-th (a total of $r - l + 1$ orbs), which consumes $y$ stamina.

Clearly, Chiaro can always complete this test using only the two spells mentioned above. However, this wizardry exam has just begun, and there are many more difficult tasks ahead. Therefore, Chiaro wants to complete this test using the minimum amount of stamina. Please help her calculate the minimum stamina required to complete this test.

Input

The first line contains three non-negative integers $n, x, y$ ($1 \le n \le 3 \times 10^5, 0 \le x, y \le 10^7$).

The next line contains $n$ non-negative integers representing the sequence $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$).

Output

A single integer representing the minimum stamina consumed.

Examples

Input 1

6 1 1
1 1 4 5 1 4

Output 1

9

Input 2

5 2 5
10 7 9 0 3

Output 2

32