Флагштокинг
(Время: 1 сек. Память: 64 Мб Сложность: 33%)
На всемирный чемпионат по Лагопроге приехали n команд. У каждой команды есть флаг, и организаторы хотят разместить их на n подготовленных флагштоках.
Высота i-го флагштока hi метров, но организаторы хотят, чтобы максимальная разница высот двух флагштоков не превосходила
D метров.
К счастью, на площадке проведения есть опытный флагштокер. За одну секунду он может поднять или опустить любой флагшток на один метр.
Определите минимальное время, которое нужно потратить флагштокеру, чтобы выполнить поставленную задачу.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n и D — количество флагштоков и максимальная допустимая разница (1 ≤ n ≤ 2×105; 0 ≤ D ≤ 109).
Вторая строка содержит n целых чисел: h1, h2, …, hn (1 ≤ hi ≤ 109). Число hi обозначает высоту i-го флагштока.
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное количество секунд, за которое можно изменить высоты флагштоков требуемым образом. То есть так, чтобы для любых двух флагштоков модуль разности их высот не превосходил D.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 4
4 2 8 1 10 | 7 |
| 2 | 6 0
1 2 3 4 5 6 | 9 |
| 3 | 6 10
1 2 3 4 5 6 | 0 |
Примечание
В первом примере, как один из вариантов, нужно поднять второй и четвёртый флагштоки до высоты 3 метра (на это потребуется 3 секунды), а третий и пятый опустить до высоты 7 метров (на это потребуется 4 секунды).
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
