题目描述

Bajtazar 遇到了一个绝佳的机会：他可以低价购买大量砾石。他想用这些砾石来平整自家花园中的一条小路。这条小路由 $n$ 段组成，初始高度分别为 $a_1, \dots, a_n$。每倾倒一车砾石，可以将某一段小路的高度提升 $1$。Bajtazar 希望小路不要太陡峭：相邻两段之间的高度差不超过 $k$。Bajtazar 最少需要购买多少车砾石，才能实现他的目标？

输入格式

输入的第一行包含两个整数 $n$ 和 $k$（其中 $1 \le n \le 1000$，$0 \le k \le 1\,000\,000$），分别表示小路的段数和相邻两段之间允许的最大高度差。

输入的第二行包含 $n$ 个整数 $a_i$（其中 $0 \le a_i \le 1\,000\,000$），表示各段小路的初始高度。

输出格式

输出一个整数：平整小路所需的最少砾石车数。

4 2
7 3 0 2

5

提示

样例解释：我们可以将第二段小路提升 $2$，至高度 $5$，将第三段小路提升 $3$，至高度 $3$。请注意，不允许降低任何一段小路的高度。