Bajtazar 遇到了一个绝佳的机会：他可以低价购买大量的碎石。他想用这些碎石来平整他花园里的一条小路。这条小路包含 $n$ 个路段，初始高度分别为 $a_1, \dots, a_n$。每倒入一卡车碎石，可以将其中一个路段的高度提高 $1$。Bajtazar 希望这条路不要太陡：相邻路段之间的高度差应不超过 $k$。为了实现这个目标，Bajtazar 最少需要购买多少卡车碎石？

输入格式

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

输出格式

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

样例

输入格式 1

4 2
7 3 0 2

输出格式 1

5

说明

我们可以将第二个路段的高度提高 $2$，使其达到 $5$；将第三个路段的高度提高 $3$，使其达到 $3$。请注意，不允许降低任何路段的高度。