Minimized Signal Transmission Time

There is a road along which m signal stations are arranged from left to right. Initially, they are numbered 1,2,…,m in order, and each pair of adjacent stations is 1 unit apart. A signal can be transmitted from a station only to any station on its right by a normal transmission (costing 1 unit time per unit distance). At the left end of the road there is a control tower located exactly 1 unit to the left of the leftmost station. The control tower is capable of bidirectional transmissions with any signal station by a special transmission (costing k time per unit distance).

You are given a signal transmission sequence S of length n (i.e. S₁, S₂, …, S_n), which obeys the following rules:

1. There are exactly n − 1 transmissions. The i-th transmission sends a signal from station S_i to station S_i+1.
2. If station S_i+1 is to the right of station S_i (i.e. after reordering, its position is greater), then a normal transmission is used, with a cost equal to the difference in positions.
3. If station S_i+1 is to the left of station S_i, then a special transmission is used. In this case, the signal is first sent from S_i to the control tower and then from the tower to S_i+1. Since the control tower is located 1 unit to the left of the leftmost station, if a station is assigned position p (with positions being consecutive positive integers), then its distance to the control tower is p. Hence the cost of the special transmission is k × (p_Si + p_Si+1).
4. If S_i = S_i+1, no transmission is needed.

The twist is that you are allowed to rearrange (i.e. permute) the order of the signal stations arbitrarily. After reordering, the stations will occupy positions 1, 2, …, m (from left to right) and the control tower will be at position 0 (which is 1 unit to the left of position 1). Your task is to determine the minimum total transmission time for the sequence S after an optimal rearrangement of the stations.

The cost for a transmission from station u (at position p_u) to station v (at position p_v) is computed as follows:

• If p_u < p_v (i.e. v is to the right of u): cost = p_v − p_u.
• If p_u > p_v (i.e. v is to the left of u): cost = k × (p_u + p_v).

Input and Output

inputFormat

The first line contains three integers m, n, and k — the number of signal stations, the length of the signal transmission sequence, and the cost multiplier for special transmissions, respectively.

The second line contains n integers S₁, S₂, …, S_n — the signal transmission sequence.

You may assume that all station labels are between 1 and m. Note that the sequence may contain duplicate values, and only the stations that appear in S affect the cost.

outputFormat

Output a single integer — the minimum total transmission time achievable by optimally rearranging the signal stations.

sample

3 4 2
1 3 2 3

11