There are $m$ signal stations arranged from left to right on a road, initially numbered $1, 2, \dots, m$ from left to right, with a distance of $1$ unit between adjacent stations. Each signal station can only transmit signals to any station to its right (called a "normal transmission"), which consumes $1$ unit of time per unit distance. A control tower is located at the far left of the road, $1$ unit of distance to the left of the leftmost signal station. The control tower can perform bidirectional signal transmission with any signal station (called a "special transmission"), but this consumes $k$ units of time per unit distance. For a given signal transmission sequence $S$ of length $n$, the transmission rules are as follows:

1. There are $n-1$ signal transmissions in total, where the $i$-th transmission sends the signal from station $S_i$ to station $S_{i+1}$.
2. If station $S_{i+1}$ is to the right of station $S_i$, a normal transmission is used, sending the signal directly from $S_i$ to $S_{i+1}$.
3. If station $S_{i+1}$ is to the left of station $S_i$, a special transmission is used: the signal is sent from $S_i$ to the control tower, and then from the control tower to $S_{i+1}$.
4. If $S_i = S_{i+1}$, no transmission is required.

As the chief engineer, Aki can swap the positions of any two signal stations any number of times, meaning he can rearrange the order of the signal stations, which will change the transmission time consumed by $S$. Now, Aki wants to know the minimum transmission time $S$ can consume after he rearranges the order of the signal stations.

Input

The first line contains three integers $n, m, k$, representing the length of the signal transmission sequence $S$, the number of signal stations, and the time consumed per unit distance for a special transmission, respectively.

The second line contains $n$ integers, where the $i$-th integer represents $S_i$.

Output

A single integer representing the answer.

Examples

Input 1

3 3 1
1 2 3

Output 1

2

Note 1

The order of the signal stations remains unchanged. Two normal transmissions are used, resulting in a time consumption of $1 + 1 = 2$.

Input 2

4 3 1
1 2 3 1

Output 2

6

Note 2

For the permutation $1, 2, 3$, the transmission time is $1 + 1 + (3\times1 + 1\times1) = 6$.

For the permutation $1, 3, 2$, the transmission time is $2 + (3\times1 + 2\times1) + (2\times1 + 1\times1) = 10$.

For the permutation $2, 1, 3$, the transmission time is $(2\times1 + 1\times1) + 2 + (3\times1 + 2\times1) = 10$.

For the permutation $2, 3, 1$, the transmission time is $(3\times1 + 1\times1) + 1 + 1 = 6$.

For the permutation $3, 1, 2$, the transmission time is $1 + (3\times1 + 1\times1) + 1 = 6$.

For the permutation $3, 2, 1$, the transmission time is $(3\times1 + 2\times1) + (2\times1 + 1\times1) + 2 = 10$.

Input 3

See the provided files.

Subtasks

$30\%$ of the data: $m\le 8, n\le 100$.

$60\%$ of the data: $m\le 20$.

$70\%$ of the data: $m\le 21$.

$80\%$ of the data: $m\le 22$.

$100\%$ of the data: $2\le m\le23, 2\le n\le 10^5, 1\le k\le 100, 1\le S_i\le m$.