Description

On a road, there are $m$ signal stations arranged from left to right. Initially, they are numbered $1,2,\dots,m$ from left to right, and the distance between any two adjacent stations is $1$ unit.

Each signal station can only transmit a signal to any station on its right (called normal transmission). It takes $1$ unit of time per unit distance.

At the far left of the road, there is a control tower. It is to the left of the leftmost signal station, with a distance of $1$ unit between them. The control tower can transmit signals bidirectionally with any signal station (called special transmission), but it takes $k$ units of time per unit distance.

Given a signal transmission sequence $S$ of length $n$, the transmission rules are:

1. There are $n-1$ transmissions in total. In the $i$-th transmission, the signal is sent from station $S_i$ to station $S_{i+1}$.
2. If station $S_{i+1}$ is to the right of station $S_i$, use normal transmission, sending directly from $S_i$ to $S_{i+1}$.
3. If station $S_{i+1}$ is to the left of station $S_i$, use special transmission: 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 needed.

Aki, as a chief engineer, can swap the positions of any two signal stations any number of times, i.e., he can reorder the signal stations. This will change the total time consumed by $S$. Now Aki wants to know: after reordering the signal stations, what is the minimum possible total transmission time for $S$?

Input Format

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 cost per unit distance for special transmission.

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

Output Format

Output one integer in a single line, representing the answer.

3 3 1
1 2 3

2

4 3 1
1 2 3 1

6

Hint

[Sample Explanation $1$]

Keeping the signal station order unchanged, normal transmission is used twice, and the time cost is $1+1=2$.

[Sample Explanation $2$]

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

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

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

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

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

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

[Constraints]

$30\%$ of the testdata: $m\leq 8, n\leq 100$.

$60\%$ of the testdata: $m\leq 20$.

$70\%$ of the testdata: $m\leq 21$.

$80\%$ of the testdata: $m\leq 22$.

$100\%$ of the testdata: $2\leq m\leq 23$, $2\leq n\leq 10^5$, $1\leq k\leq 100$, $1\leq S_i\leq m$.

Translated by ChatGPT 5