Safe Art Exhibition

Squeaky, a little mouse, has recently taken an interest in visual art and is showcasing his work at the city’s most prestigious art festival. His artwork consists of N glowing pillars arranged in a line. The i-th pillar is built by stacking S_i glowing cubes. For safety reasons, the installation must satisfy the following condition:

$$|S_i - S_{i+1}| \le H,\quad \forall\, 1 \le i < N.$$

However, the original configuration might be unsafe. Squeaky can only modify his work using the following operations:

• Add one cube to pillar k (i.e. S_k <- S_k + 1).
• Remove one cube from pillar k if it has at least one cube (i.e. S_k <- S_k - 1).

Even if a pillar has zero cubes, it is still considered to exist at its original position. Your task is to determine the minimum number of modifications needed to achieve a safe configuration.

inputFormat

The first line contains two integers N and H (1 ≤ N ≤ 200, 0 ≤ H ≤ 10⁹), representing the number of pillars and the maximum allowed difference between adjacent pillars, respectively.

The second line contains N integers: S₁, S₂, ..., S_N (0 ≤ S_i ≤ 10⁹), where S_i is the height of the i-th pillar (i.e. the number of glowing cubes in pillar i).

outputFormat

Output a single integer representing the minimum number of modifications required so that the artwork becomes safe.

sample

3 1
1 3 1

1