Bajtazar has come across an amazing opportunity: he can buy a large amount of gravel at a low price. He wants to use it to level a path in his garden. The path consists of $n$ segments, initially at heights $a_1, \dots, a_n$. By adding one truckload of gravel, he can increase the height of one path segment by 1. Bajtazar would like the path not to be too steep: the difference between adjacent path segments should be at most $k$. What is the minimum number of truckloads of gravel Bajtazar must purchase to achieve his goal?

Input

The first line of input contains two integers $n$ and $k$ (where $1 \le n \le 1\,000$ and $0 \le k \le 1\,000\,000$), representing the length of the path and the maximum allowed height difference between consecutive path segments, respectively. The second line of input contains $n$ integers $a_i$ (where $0 \le a_i \le 1\,000\,000$); these are the initial heights of the consecutive path segments.

Output

Output a single integer: the minimum number of truckloads of gravel needed to level the path.

Examples

Input 1

4 2
7 3 0 2

Output 1

5

Note

Explanation of the example: We can raise the second segment of the path by 2, to a height of 5, and the third segment of the path by 3, to a height of 3. Note that it is not allowed to lower any of the path segments.