[AdditionalFile5678.zip](file://AdditionalFile5678.zip?type=additional_file)

#5678. 「PA 2026」Dostawa żwiru

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 2 Dostawa żwiru

Bajtazar 遇到一个绝佳机会：他可以廉价购入大量的碎石。他想利用这些碎石来铺平花园里的一条小路。这条小路包含 $n$ 个路段，初始高度分别为 $a_{1}, \ldots, a_{n}$。每倒入一车碎石，可以将一个小路段的高度提升 $1$ 个单位。Bajtazar 希望小路不会太陡：相邻两个路段之间的高度差不能超过 $k$。为了实现这个目标，Bajtazar 至少需要购买多少车碎石？

输入格式

第一行输入包含两个整数 $n$ 和 $k$ $(1 \leq n \leq 1000, 0 \leq k \leq 1000000)$，分别表示小路的长度以及相邻路段之间允许的最大高度差。

第二行包含 $n$ 个整数 $a_{i}$ $(0 \leq a_{i} \leq 1000000)$，代表小路各路段的初始高度。

输出格式

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

样例

输入

4 2
7 3 0 2

输出

5

我们可以将第二个路段的高度提升 $2$ 至高度 $5$，将第三个路段的高度提升 $3$ 至高度 $3$。此时路段高度序列变为 $7, 5, 3, 2$。相邻路段高度差分别为 $|7-5|=2, |5-3|=2, |3-2|=1$，均不超过 $k=2$。请注意，不允许降低任何路段的高度。