Ở sâu trong vùng nông thôn, những chú bò của Farmer John không chỉ là những vật nuôi bình thường — chúng là thành viên của một mạng lưới tình báo bò bí mật. Mỗi con bò mang một mã số ID được các chuyên gia mật mã bò tinh nhuệ gán cẩn thận. Tuy nhiên, do hệ thống gắn thẻ khá tùy tiện của Farmer John, một số con bò có cùng ID.

Farmer John ghi nhận có \(N\) (\(1\le N\le 2\cdot 10^5\)) giá trị ID phân biệt; với mỗi ID phân biệt \(d_i\) (\(0\le d_i\le 10^9\)), có \(n_i\) (\(1\le n_i\le 10^9\)) con bò cùng mang ID đó.

Các con bò chỉ có thể liên lạc theo cặp, và phương thức mã hóa bí mật của chúng có một quy tắc nghiêm ngặt: hai con bò chỉ có thể trao đổi thông tin nếu chúng không phải cùng một con và tổng ID của chúng bằng \(A\) hoặc \(B\) (\(0\le A\le B\le 2\cdot 10^9\)). Mỗi con bò chỉ có thể tham gia một cuộc trò chuyện tại một thời điểm (tức là không con bò nào thuộc nhiều hơn một cặp).

Farmer John muốn tối đa hóa số cặp liên lạc rời nhau để luồng thông tin đạt hiệu quả cao nhất. Hãy xác định số cuộc trò chuyện lớn nhất có thể diễn ra đồng thời.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(A\), \(B\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(n_i\) và \(d_i\). Không có hai giá trị \(d_i\) nào bằng nhau.

Dữ liệu ra

In ra số cặp bò liên lạc rời nhau lớn nhất có thể được tạo thành cùng lúc.

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu số nguyên 64-bit (chẳng hạn long long trong C/C++).

Ví dụ

4 4 5
17 2
100 0
10 1
200 4

118

4 4 5
100 0
10 1
100 3
20 4

30

Phân nhóm

• Dữ liệu 3–4: \(A=B\).
• Dữ liệu 5–7: \(N\le 1000\).
• Dữ liệu 8–12: Không có ràng buộc bổ sung.

Đề bài: Benjamin Qi.

Nguồn

USACO 2025 US Open Contest, Silver — Compatible Pairs: https://usaco.org/index.php?page=viewproblem2&cpid=1519