Ski Resort Construction Optimization

JOI has managed a famous ski resort on the IOI Plateau for many years. To celebrate the 15th anniversary of its opening, he plans to build a new ski resort on the adjacent KOI Plateau. The KOI Plateau has N points numbered from 1 to N. The initial elevation of point i is \(H_i\) (in meters). There are no slopes initially, but each point is equipped with one unused connection facility.

The construction will proceed in four steps:

1. Embankment work (can be performed any number of times, including zero): choose a point \(i\) and increase its elevation by 1 meter. Each operation costs \(K\).
2. Hotel construction: choose one of the \(N\) points and build the KOI hotel there.
3. Expansion work (can be performed any number of times, including zero): choose a point \(i\) and construct an additional connection facility at that point at a cost of \(C_i\) per facility.
4. Slope construction: For every point (except the hotel), choose another point with strictly lower elevation that has an unused connection facility, and construct a one‐way slope from the higher point to that lower point. (Note that each connection facility may be used at most once.) If it becomes impossible to choose such a point for some non‐hotel point, the construction fails.

The overall cost of building the ski resort is the sum of the costs incurred by the embankment work and the expansion work. JOI's objective is to make the resort accessible, i.e. from any point one should be able to ski via a sequence of slopes to the hotel, while minimizing the total cost.

Observation: One way to guarantee accessibility is to arrange the points in a chain in which the hotel is at the lowest elevation and every other point has a parent with a strictly lower elevation. In such a chain, for every non‐hotel point, we can assign the slope to the immediately preceding point. Each point initially has one connection facility, which is enough to serve as a parent for one slope. Therefore, if we can reassign the elevations (only by increasing them) such that they are strictly increasing in some order, no extra expansion work is needed. The cost is then the sum of elevation increments.

More formally, if we choose a permutation \(P = (P[1], P[2], \ldots, P[N])\) of the points with the hotel at \(P[1]\) and set the final elevation \(A_{P[1]} = H_{P[1]}\) and for \(k \ge 2\) \[ A_{P[k]} = \max\bigl(H_{P[k]}, A_{P[k-1]} + 1\bigr), \] then the embankment cost is \(\sum_{k=1}^N (A_{P[k]} - H_{P[k]})\) and the expansion cost is 0 (since a chain uses each point's free connection facility exactly once).

It can be shown that the optimal ordering is to sort the points in non-decreasing order of \(H_i\). Your task is to compute the minimum total cost required to build the resort.

Input Constraints:

• \(1 \le N \le \text{(some large number)}\).
• \(H_i\) and \(K\), \(C_i\) are integers. (Note: In the optimal solution described, expansion work is unnecessary.)

inputFormat

The first line contains an integer \(N\) representing the number of points on the plateau.

The second line contains \(N\) space‐separated integers \(H_1, H_2, \ldots, H_N\) representing the initial elevations of the points.

The third line contains an integer \(K\) representing the cost of increasing the elevation by 1 meter. (Note: Although expansion work costs \(C_i\) are defined in the problem, an optimal solution does not require any expansion work.)

outputFormat

Output a single integer, the minimum total cost required to build the ski resort.

sample

2
5 5
3

1

</p>