Problems
Deep in the countryside, Farmer John's cows aren’t just ordinary farm animals — they are part of a clandestine bovine intelligence network. Each cow carries an ID number, carefully assigned by the elite cow cryptographers. However, due to Farmer John's rather haphazard tagging system, some cows ended up with the same ID.
Farmer John noted that there are N (1 ≤ N ≤ 2·10^5) unique ID numbers, and for each unique ID d_i (0 ≤ d_i ≤ 10^9), there are n_i (1 ≤ n_i ≤ 10^9) cows who share it.
The cows can only communicate in pairs, and their secret encryption method has one strict rule: two cows can only exchange information if they are not the same cow and the sum of their ID numbers equals either A or B (0 ≤ A ≤ B ≤ 2·10^9). A cow can only engage in one conversation at a time (i.e., no cow can be part of more than one pair).
Farmer John would like to maximize the number of disjoint communication pairs to ensure the best information flow. Can you determine the largest number of conversations that can happen at once?
Input
The first line contains three integers N, A, and B.
The next N lines each contain two space-separated integers n_i and d_i. No two d_i are the same.
Output
Print a single line containing the maximum number of disjoint communicating pairs that can be formed at the same time.
Example #1
4 4 5
17 2
100 0
10 1
200 4
118
A cow with an ID of 0 can communicate with another cow with an ID of 4 because the sum of their IDs is 0 + 4 = 4. There are 100 cows with ID 0 and 200 cows with ID 4, allowing up to 100 communicating pairs for this combination.
Additionally, a cow with an ID of 4 can communicate with a cow with an ID of 1 (since 4 + 1 = 5). With 10 cows of ID 1 and 100 remaining unpaired cows of ID 4, an extra 10 pairs can be formed.
Finally, cows with ID 2 can pair among themselves because 2 + 2 = 4. With 17 cows having ID 2, up to 8 pairs can be formed.
In total, there are 100 + 10 + 8 = 118 disjoint pairs.
Example #2
4 4 5
100 0
10 1
100 3
20 4
30
Pairing cows with IDs 0 and 4 can form 20 pairs, and pairing cows with IDs 1 and 3 can form 10 pairs. In total, the maximum number of disjoint communicating pairs is 20 + 10 = 30.
You must sign in to write code.