Фермер Джон заметил, что имеется \(N\) (\(1\le N\le 2\cdot 10^5\)) уникальных
ID-номеров и для каждого уникального ID \(d_i\) (\(0\le d_i\le 10^9\)),
имеется \(n_i\) (\(1\le n_i\le 10^9\)) коров с таким ID.
Эти коровы могут коммуницировать в парах, их секретный метод шифрования
имеет одно строгое правило: две коровы могут обмениваться информацией
если это не одна и та же корова и сумма их ID-номеров равна или \(A\) или \(B\)
(\(0\le A\le B\le 2\cdot 10^9\)). В один момент времени, корова может быть вовлечена только в одну беседу (то есть никакая корова не может быть частью более чем одной пары)
ФД хочет максимизировать количество коммуницирующих пар.
Определите максимальное количество бесед, которые могут состоятся в один момент времени.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\),
\(A\),
\(B\).
Каждая из последующих \(N\) строк содержит \(n_i\) и \(d_i\).
Никакие два \(d_i\) не совпадают.
ФОРМАТ ВЫВОДА (на экран / stdout):
Максимальное количество несвязных коммуницирующих пар которые могут быть сформированы
в один и тот же момент времени.
В задаче может потребоваться использование 64-битного целого типа данных
(например, "long long" в C/C++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4 5
17 2
100 0
10 1
200 4
|
118
|