Maximal Cow Communication Pairs

Farmer John’s cows are not ordinary farm animals – each cow belongs to a secret cow intelligence network and is assigned an ID by elite cryptographers. However, due to Farmer John’s careless labelling, several cows share the same ID. In total there are \(N\) unique IDs. For each unique ID \(d_i\) (with \(0\le d_i\le 10^9\)) there are \(n_i\) cows (with \(1\le n_i\le 10^9\)) that have that ID.

The cows may only communicate in pairs. Two distinct cows may only talk if the sum of their IDs equals either \(A\) or \(B\) (with \(0\le A\le B\le 2\cdot10^9\)). Furthermore, each cow may be involved in at most one communication pair at the same time.

Help Farmer John maximize the number of simultaneous communication pairs so that the cow‐network information flow is optimal.

Note on valid pairs: Two cows (which may have the same ID provided they are distinct animals) can form a pair if, for example, their IDs \(x\) and \(y\) satisfy either \[ x+y=A \quad \text{or} \quad x+y=B. \] For the special case when \(x=y\) (which is only possible if \(2x=A\) or \(2x=B\)), at least two cows having the same ID are required.

inputFormat

The first line contains three integers \(N\), \(A\) and \(B\). \(N\) is the number of unique ID numbers recorded. \(A\) and \(B\) are the two allowed sums for a communicating pair.

Then follow \(N\) lines, each containing two integers \(d_i\) and \(n_i\) which denote the ID and the number of cows having that ID.

It is guaranteed that \(1 \le N \le 2\cdot10^5\), \(0 \le d_i \le 10^9\), \(1 \le n_i \le 10^9\), and \(0 \le A \le B \le 2\cdot10^9\).

outputFormat

Output a single integer representing the maximum number of simultaneous cow communication pairs that can be formed.

Explanation: Each pair uses two cows (possibly from the same ID if valid), and each cow can be in at most one pair. A pair is valid only if the sum of the two cows' IDs equals \(A\) or \(B\).

sample

3 30 50
10 5
20 3
40 4

5