Финальное противостояние
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нео и Тринити противостоят армии ботов, заполонивших виртуальный город Сан-Франциско.

Сам город можно представить в виде бесконечной координатной прямой. Боты нападают последовательными волнами, каждая из $$$n$$$ волн представляет собой отрезок этой прямой, который целиком заполнен ботами. Нео знает, что в $$$i$$$-ю волну боты будут занимать отрезок с концами в точках $$$l_i$$$ и $$$r_i$$$ (то есть $$$[l_i, r_i]$$$).

Тринити считает группу последовательных волн с $$$a$$$-й по $$$b$$$-ю включительно опасной, если при пересечение занятых ботами в эти волны отрезков имеет длину не меньше $$$m_1$$$ и не больше $$$m_2$$$. Иными словами, пара чисел $$$(a, b)$$$, для которых $$$a \leqslant b$$$, задает опасную группу волн тогда и только тогда, когда $$$$$$m_1 \leqslant \left|\bigcap\limits_{a \leqslant i \leqslant b} [l_i, r_i] \right| \leqslant m_2\text{.}$$$$$$

Например, если $$$n = 3$$$ и $$$[l_1, r_1] = [4, 7]$$$, $$$[l_2, r_2] = [5, 8]$$$ и $$$[l_3, r_3] = [3, 6]$$$, то пересечение отрезков первых двух волн равно $$$[4, 7] \cap [5, 8] = [5, 7]$$$ и имеет длину $$$2$$$, а пересечение всех трех отрезков равно $$$[5, 6]$$$ и имеет длину $$$1$$$. При $$$m_1 = 2$$$, первые две волны вместе будут опасными, а все три вместе — нет. Обратите внимание, что если какая-то группа волн является опасной, это не значит, что любая содержащая ее группа волн также опасна.

Помогите Нео и Тринити найти количество опасных групп волн, чтобы они могли поскорее выбрать план действий.

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

В первой строке ввода через пробел даны три целых числа $$$n$$$, $$$m_1$$$ и $$$m_2$$$ — количество волн и границы допустимых значений длины пересечения отрезков ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$; $$$0 \leqslant m_1 \leqslant m_2 \leqslant 10^9$$$).

В следующих $$$n$$$ строках перечислены координаты концов отрезков, заполненных ботами: в $$$i$$$-й строке через пробел даны целые числа $$$l_i$$$ и $$$r_i$$$ — границы $$$i$$$-го отрезка ($$$0 \leqslant l_i < r_i \leqslant 10^9$$$).

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

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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты из условия, а также тесты для этой подзадачи и необходимых подзадач успешно пройдены.

|c|c|}

Подзадача

Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
112полная
218полная
3181первая ошибка
420полная
5321 – 4первая ошибка

Примеры

Входные данные
4 1 2
0 4
1 5
2 6
3 4
Выходные данные
5
Входные данные
6 0 1
0 4
0 2
0 1
3 4
2 4
0 4
Выходные данные
15

Примечание

В первом примере в качестве опасной группы подойдет любая группа, содержащая четвертую волну, так как ее длина равна $$$1$$$ и ее отрезок содержится во всех остальных отрезках, а значит и пересечение будет иметь длину $$$1$$$. А также, помимо этого, подойдет группа из первых трех волн, имеющая пересечение отрезков, равное $$$[2, 4]$$$.

Во втором примере подойдет любая группа, содержащая третью или четвертую волну. Несложно заметить, что группы, состоящие только из двух первых или двух последних волн, имеют пересечение отрезков длины хотя бы $$$2$$$. Всего таких подходящих групп ровно $$$15$$$.