eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Турист

Турист

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Турист подорожує пішки уздовж координатної вісі Ox. Йти можна в будь-якому з двох можливих напрямків та з будь-якою швидкістю, що не перевищує V, в тому числі знаходитись на місці. З газетних анонсів він знає, що у момент t_1 у точці з координатою x_1 відбудеться одна цікава подія, у момент t_2 у точці з координатою x_2 - ще одна, і т. д., до (x_N, t_N). Цікаві події достатньо короткотривалі, їх можна вважати миттєвими. Вважається, що турист відвідав подію i, якщо у момент t_i він знаходився у точці з координатою x_i.

Напишіть програму, яка знайде максимальну кількість подій, які зможе відвідати турист, для таких двох припущень:

  • спочатку руху (у момент часу 0) турист знаходиться у точці 0;

  • турист може обрати початкову точку, з якої він вирушить.

Вхідні дані

Перший рядок містить єдине натуральне число N (1 N 100 000) - кількість цікавих подій. Наступні N рядків містять по два цілих числа x_i та t_i - координату та момент часу події з номером i. Останній (N+2)-ий рядок файлу містить єдине ціле число V - значення максимальної швидкості руху туриста. Усі значення x_i належать діапазону –10^8x_i10^8, усі значення t_i належать діапазону 1t_i10^6, значення V належить діапазону 1V1000. У вхідних даних можливі різні події, що мають однакову координату x або однаковий час t, але неможливі різні події, що мають однакові x та t одночасно.

Вихідні дані

Єдиний рядок має містити два цілих числа - максимально можливу кількість подій, які турист може відвідати, якщо він розпочне рух у момент 0 з точки 0, потім максимально можливу кількість подій, які турист може відвідати, самостійно обравши точку старту.

Приклад

Вхідні дані #1
3
-1 1
42 7
40 8
2
Вихідні дані #1
1 2
Автор Ілля Порубльов
Джерело 2011 XXIV Всеукраїнська олімпіада з інформатики, Черкаси, Березень 26 - 31, тур 1