Турист#2008

Турист

1 секунда

64 мегабайти

Середня

Турист рухається віссю $X$ . Він може рухатися в будь-якому напрямку зі швидкістю, що не перевищує $V$ , або залишатися на місці. Із газетних оголошень він дізнається, що у момент часу $t_{1}$ t_1 у точці $x_{1}$ x_1 відбудеться одна цікава подія, у момент часу $t_{2}$ t_2 в точці $x_{2}$ x_2 — інша, і так далі до $(x_{N}, t_{N})$ (x_N, t_N). Цікаві події дуже короткочасні — вважаємо, що вони відбуваються миттєво. Подія $i$ вважається відвіданою, якщо у момент часу $t_{i}$ t_i турист знаходиться у точці $x_{i}$ x_i.

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

На початку руху (у момент часу $0$ ) турист перебуває у точці $0$ ;
Турист може вибрати будь-яку початкову точку.

Вхідні дані

Перший рядок містить одне ціле число $N$ ( $1 \leq N \leq 100000$ 1 \le N \le 100\,000) — кількість цікавих подій. Наступні $N$ рядків містять по два цілих числа $x_{i}$ x_i і $t_{i}$ t_i — координату і час $i$ -ї події. Останній рядок містить одне ціле число $V$ — максимальну можливу швидкість туриста. Всі $x_{i}$ x_i задовольняють $- 1 0^{8} \leq x_{i} \leq 1 0^{8}$ -10^8 \le x_i \le 10^8, всі $t_{i}$ t_i — $1 \leq t_{i} \leq 1 0^{6}$ 1 \le t_i \le 10^6, і $1 \leq V \leq 1000$ 1 \le V \le 1000. Можуть бути різні події з однаковими координатами $x$ або з однаковими моментами часу $t$ , але не з однаковими $x$ і $t$ одночасно.

Вихідні дані

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

Приклади

Приклад 1