2010. Забор

Петя решил сделать небольшой забор из нескольких имеющихся у него досок разной длины. Из эстетических соображений разница в длине планок забора не должна превышать некоторой величины `D`. Петя может разрезать доску на любое количество планок, имеющих любую длину. Необязательно, чтобы их длина была целым числом или планки из одной доски имели одинаковую длину. Но после разрезания нельзя выбрасывать ничего – все отрезанные от доски части становятся планками забора. Так как Пете приходится пилить доски ножовкой (вручную), то он хочет минимизировать количество распилов.

Напишите программу, которая подсчитает минимальное количество распилов для заданного набора досок на планки, при котором разница в длине между самой длинной и самой короткой планкой не будет превышать `D`.

Первая строка ввода содержит два целых числа — количество досок `N` (`2\ ≤\ N\ ≤\ 1000`) и ограничение по разнице длин планок `D` (`100\ ≤\ D\ ≤\ 1000`). Во второй строке содержится `N` целых чисел в диапазоне от 1000 до 100000 — длины досок.

Вывести одно целое число — минимальное количество распилов.

2 100
1600 1100

3

Пояснение к примеру: Петя может первую доску распилить на планки длиной 500, 500 и 600 с помощью двух распилов, а вторую доску – на две планки длиной 500 и 600. Это не единственный вариант. Можно распилить вторую доску на части длиной 501 и 599 или 502.36 и 597.64.

Характеристика тестов к задаче:

Для 10-11 классов в 20% тестов `N=2`, в 30% тестов `N=10`, в 50% тестов `N=1000`.

Для 7-9 классов `N≤10` и использовалась половина всех тестов, в 40% тестов `N=2`, в 60% тестов `N=10`.