Хмарочоси
Через 5000 років після зупинки епідемії коронавірусу в Баку планується зведення n хмарочосів. Ми будемо розглядати Баку як координатну вісь чисел. Для кожного хмарочоса задано його координату (x[i]
) на цій осі та висоту (h[i]
). Інженери вважають хмарочос "невигідним", якщо зліва від нього на відстані не більше d, а також справа від нього на відстані не більше d, розташований хмарочос, висота якого щонайменше вдвічі більша за висоту даного хмарочоса (цей хмарочос також може бути невигідним). Такі хмарочоси вважаються неуспішними з точки зору бізнесу, тому інженери планують замінити їх іншими об'єктами. Ваше завдання — підрахувати кількість "невигідних" хмарочосів, щоб інженери могли прийняти відповідні рішення.
Вхідні дані
Перший рядок містить два числа: n (1 ≤ n ≤ 10^5
) та d (1
≤ d ≤ 10^9
). У наступних n рядках наведені числа x[i]
та h[i]
(1 ≤ x[i]
, h[i]
≤ 10^9
). Усі координати хмарочосів є унікальними.
Вихідні дані
Виведіть кількість невигідних хмарочосів.