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$。請注意，不允許降低任何區段的高度。