Problem Description

Bajtazar came across a great opportunity: he can buy a large amount of gravel at a low price. He wants to use this gravel to level a small path in his garden. The path consists of $n$ segments, with initial heights $a_1, \dots, a_n$. Each time he dumps one truckload of gravel, he can increase the height of one segment of the path by $1$. Bajtazar wants the path not to be too steep: the height difference between any two adjacent segments must not exceed $k$. What is the minimum number of truckloads of gravel Bajtazar needs to buy to achieve his goal?

Input Format

The first line contains two integers $n$ and $k$ ($1 \le n \le 1000$, $0 \le k \le 1\,000\,000$), representing the number of segments of the path and the maximum allowed height difference between adjacent segments.

The second line contains $n$ integers $a_i$ ($0 \le a_i \le 1\,000\,000$), representing the initial height of each segment.

Output Format

Print one integer: the minimum number of truckloads of gravel required to level the path.

4 2
7 3 0 2

5

Hint

Sample explanation: We can raise the second segment by $2$ to height $5$, and raise the third segment by $3$ to height $3$. Note that it is not allowed to decrease the height of any segment.

Translated by ChatGPT 5