Description

There are $n$ sentry stations arranged in a line. The frequency band of station $i$ is $a_i$.

Each station $i$ needs to choose one of the following two options:

1. Connect directly to the control center, with a cost of $W$.
2. Connect to some previous station $j$ ($j<i$), with a cost of $|a_i-a_j|$.

Each station can be connected by at most one later station.

Please find the minimum possible total cost.

Input Format

The first line contains two non-negative integers $n, W$, representing the number of sentry stations and the cost to connect to the control center.

The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$ separated by spaces, representing the frequency band of each station in order.

Output Format

Output one line containing one non-negative integer, representing the answer.

6 7
8 4 6 1 3 0

23

8 4
0 4 2 6 1 5 3 7

18

Hint

For all testdata, $1 \leq n \leq 1000$, $0 \leq W, a_i \leq 10^9$.

For $10\%$ of the testdata, $n \leq 10$.

For another $10\%$ of the testdata, $n \leq 20$.

For another $20\%$ of the testdata, $n \leq 50$, $W \leq 5$, $a_i \leq 4$.

For another $20\%$ of the testdata, $n \leq 100$.

For another $20\%$ of the testdata, $n \leq 300$.

For the remaining $20\%$ of the testdata, there are no special constraints.

Translated by ChatGPT 5