Minimum Communication Cost

There are (n) sentry posts arranged in a line. The (i)-th sentry post has a frequency band given by (a_i). Each sentry post (i) must decide one of the following:

1. Connect directly to the control centre with a cost (W).
2. Connect to some previous sentry post (j) (with (j < i)) with a cost (|a_i - a_j|).

However, each sentry post can be used as the connection target by at most one later sentry post.

Under these conditions, find the minimum total cost required to connect all sentry posts.

A useful observation is that if no pairing is used then the total cost is (n \times W). When a sentry post (i) chooses to connect to a previous post (j) ((j < i)) instead of connecting directly, the cost for (i) becomes (|a_i - a_j|) rather than (W). If (|a_i - a_j| < W), a saving of (W - |a_i - a_j|) is achieved. But since each post can be used at most once as a target, these beneficial pairings must be chosen without conflict. It can be shown that there exists an optimal solution in which the chosen pairs do not cross (i.e. if posts (i) and (j) are paired and posts (p) and (q) are paired with (i < p < j < q), then one can rearrange the pairing without reducing the total saving).

Thus, let the baseline cost be (n \times W). We wish to select a set of non‐crossing pairs ((j,i)) (with (j < i)) for which (W - |a_i - a_j| > 0] such that the total saving (\sum (W - |a_i - a_j|)) is maximized. The answer is then (n \times W - \text{(maximum total saving)}).

inputFormat

The first line contains two integers \(n\) and \(W\) (the number of sentry posts and the direct connection cost).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), where \(a_i\) represents the frequency band of the \(i\)-th sentry post.

outputFormat

Output a single integer — the minimum total cost to connect all sentry posts.

sample

3 3
1 3 4

7