D. Лунная тень
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Сумерки охватывают леса и весь мир. Реку и лодку освещает луна.

— Сложно возможно затмить свет луны. Тени лишь раскрывают ее красоту и мягкость, — пропел Мино.

— Видишь? Облака, — сказал Канно, вглядываясь вдаль.

— Не может быть ничего лучше, — обернулся Мино к Канно.

Представим небо как координатную ось. Луна находится в начале координат, то есть в точке с координатой $$$0$$$.

В небе есть $$$n$$$ облаков. Все облака имеют одинаковую длину $$$l$$$. $$$i$$$-е облако изначально покрывает отрезок $$$(x_i, x_i + l)$$$ (не включая границы). Изначально облако двигается со скоростью $$$v_i$$$, которая равна либо $$$1$$$, либо $$$-1$$$.

Изначально никакие два облака не пересекаются, то есть для всех $$$1 \leq i \lt j \leq n$$$ выполняется $$$\lvert x_i - x_j \rvert \geq l$$$.

Если скорость ветра равна $$$w$$$, то скорость $$$i$$$-го облака станет равна $$$v_i + w$$$, то есть его координаты будут увеличиваться на $$$v_i + w$$$ за единицу времени. Обратите внимание, ветер может быть достаточно сильным и направления движения облаков могут изменяться.

Помогите Мино, подсчитайте число пар $$$(i, j)$$$ ($$$i < j$$$) таких, что существует такая скорость ветра $$$w$$$, не превышающая $$$w_\mathrm{max}$$$ по модулю (возможно, отрицательная и/или вещественная) такая, что $$$i$$$-е и $$$j$$$-е облака в какой-то момент будут оба закрывать луну. Скорость ветра $$$w$$$ может быть различной для различных пар.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$l$$$ и $$$w_\mathrm{max}$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq l, w_\mathrm{max} \leq 10^8$$$) — количество облаков, длина каждого облака и максимально возможная скорость ветра, соответственно.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$ и $$$v_i$$$ ($$$-10^8 \leq x_i \leq 10^8$$$, $$$v_i \in \{-1, 1\}$$$) — начальная позиция и скорость $$$i$$$-го облака, соответственно.

Гарантируется, что для всех $$$1 \leq i \lt j \leq n$$$ выполняется $$$\lvert x_i - x_j \rvert \geq l$$$.

Выходные данные

Выведите одно целое число — количество неупорядоченных пар облаков таких, что они могут закрыть луну в один и тот же момент при некотором выборе скорости ветра $$$w$$$.

Примеры
Входные данные
5 1 2
-2 1
2 1
3 -1
5 -1
7 -1
Выходные данные
4
Входные данные
4 10 1
-20 1
-10 -1
0 1
10 -1
Выходные данные
1
Примечание

В первом примере начальные позиции и скорости облаков проиллюстрированы на рисунке ниже.

Пары облаков, которые могут одновременно закрыть луну:

  • $$$(1, 3)$$$ закроют луну в момент времени $$$2.5$$$ при $$$w = -0.4$$$;
  • $$$(1, 4)$$$ закроют луну в момент времени $$$3.5$$$ при $$$w = -0.6$$$;
  • $$$(1, 5)$$$ закроют луну в момент времени $$$4.5$$$ при $$$w = -0.7$$$;
  • $$$(2, 5)$$$ закроют луну в момент времени $$$2.5$$$ при $$$w = -2$$$.

На рисунке ниже приведены положения облаков в момент времени $$$2.5$$$ при скорости ветра $$$w = -0.4$$$. В этот момент $$$1$$$-е и $$$3$$$-е облака оба закрывают луну.

Во втором примере только пара $$$(1, 4)$$$ закроют луну в момент времени $$$15$$$ при скорости ветра $$$w = 0$$$.

Обратите внимание, что все времена и скорости ветра в примечании даны для примера, на самом деле существует бесконечное число способов выбрать их.