$n$ outposts arranged in a line need to communicate. The frequency of the $i$-th outpost is $a_i$.
Each outpost $i$ must choose one of the following two options:
- Connect directly to the control center, with a cost of $W$;
- Connect to a preceding outpost $j$ ($j < i$), with a cost of $|a_i - a_j|$.
Each outpost can be connected to by at most one subsequent outpost.
Find the minimum possible total cost.
Input
The first line contains two natural numbers $n$ and $W$, representing the number of outposts and the cost to connect to the control center, respectively.
The second line contains $n$ space-separated natural numbers $a_1, a_2, \dots, a_n$, representing the frequency of each outpost in order.
Output
Output a single natural number representing the answer.
Examples
Input 1
6 7 8 4 6 1 3 0
Output 1
23
Note 1
If we denote the control center as $0$, in the optimal solution, the outposts that each outpost connects to are $0, 0, 1, 2, 3, 4$ respectively.
Input 2
8 4 0 4 2 6 1 5 3 7
Output 2
18
Subtasks
For all data, $1 \le n \le 1000, 0 \le W, a_i \le 10^9$.
- For $10\%$ of the data, $n \le 10$;
- For another $10\%$ of the data, $n \le 20$;
- For another $20\%$ of the data, $n \le 50, W \le 5, a_i \le 4$;
- For another $20\%$ of the data, $n \le 100$;
- For another $20\%$ of the data, $n \le 300$;
- For the remaining $20\%$ of the data, there are no special restrictions.