L. Karst
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On his search for habitable planets, Johnny discovered the planet Karst. However, even though Karst has the perfect atmosphere, temperature, and gravity for human living, there's one major problem: Karst's surface is too rough!

The surface of Karst can be represented by a sequence of $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ representing altitudes measured at various locations on the planet. Johnny would like the surface of Karst to be smoothed out such that the new measured altitudes form a sequence $$$b_1, b_2, ..., b_n$$$. In particular, for some smoothness value $$$k$$$, the new sequence should satisfy $$$|b_i - b_{i + 1}| \le k$$$ for $$$1 \le i \le n - 1$$$.

Fortunately, Johnny has many AI terraforming agents at his disposal, which will perform any surface transformation with cost $$$\sum_{i = 1}^n |a_i - b_i|$$$. Since Johnny does not want to use up all the water on his home planet to power his AI agents, he would like to know: What is the minimum cost to smooth out the surface of Karst?

Input

The first line contains two integers, $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) – the number of altitude measurements and the desired smoothness value, respectively.

The next line contains $$$n$$$ space-separated integers, with the $$$i$$$-th integer being $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) – the $$$i$$$-th measured altitude on Karst.

Output

Output a single integer – the minimum cost to smooth out the surface of Karst.

Example
Input
3 1
5 7 5
Output
1
Note

In the sample test case, Johnny can achieve the minimum cost of $$$1$$$ with the sequence $$$b_1 = 5$$$, $$$b_2 = 6$$$, and $$$b_3 = 5$$$. Observe that this sequence also satisfies the smoothness value of $$$1$$$.