Байтазару представилась невероятная возможность: он может дешево купить большое количество гравия. Он хочет использовать его, чтобы выровнять дорожку в своем саду. Дорожка состоит из $n$ фрагментов, которые изначально находятся на высотах $a_1, \dots, a_n$. Досыпав одну машину гравия, можно увеличить высоту одного фрагмента дорожки на 1. Байтазар хочет, чтобы дорожка не была слишком крутой: разница между соседними фрагментами дорожки должна составлять не более $k$. Какое минимальное количество машин гравия должен купить Байтазар, чтобы достичь своей цели?

Входные данные

В первой строке входных данных находятся два целых числа $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

Пояснение к примеру: мы можем поднять второй фрагмент дорожки на 2, до высоты 5, а третий фрагмент дорожки на 3, до высоты 3. Обратите внимание, что понижение любого из фрагментов дорожки не допускается.