C. Clamped Sequence
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Given an integer sequence $$$a_1, a_2, \ldots, a_n$$$ and a positive integer $$$d$$$, you need to clamp the sequence to a range $$$[l,r]$$$ satisfying $$$0 \le r-l \le d$$$ that maximize $$$\sum_{i=1}^{n-1}|a_i - a_{i+1}|$$$, where $$$|x|$$$ is the absolute value of $$$x$$$.

More specifically, clamping the sequence to the range $$$[l,r]$$$ makes each element

$$$$$$ a_i := \left\{ \begin{array}{rcl} l, & a_i \lt l; \\ a_i, & l \le a_i \le r; \\ r, & a_i \gt r. \\ \end{array} \right. $$$$$$

Both $$$l$$$ and $$$r$$$ are arbitrary real numbers decided by you under the given constraints. It can be shown that the maximum sum is always an integer.

Input

The first line contains two integers $$$n$$$ ($$$2\le n\le 5\,000$$$) and $$$d$$$ ($$$1\le d\le 10^9)$$$, denoting the length of the given sequence and the given parameter respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$), denoting the given sequence.

Output

Output a line containing a single integer, denoting the maximum sum.

Example
Input
8 3
3 1 4 1 5 9 2 6
Output
15
Note

In the sample case, you can clamp the given sequence to the range $$$[1,4]$$$ to make it $$$[3,1,4,1,4,4,2,4]$$$, and the resulting sum is the maximum $$$15$$$.