P6622 [NOI Qualifier Joint Contest 2020 A/B Paper] Signal Transmission.

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$?

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 one integer in a single line, representing the answer.

[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