题目描述

在遥远的乡村，农夫约翰的奶牛并非普通的农场动物——它们隶属于一个秘密的奶牛情报网络。每头奶牛都有一个由精英密码学家精心分配的ID号码。但由于农夫约翰随意的标记系统，部分奶牛出现了重复ID的情况。

农夫约翰记录到共有 $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$）时才能交换信息。每头奶牛同一时间只能参与一次对话（即不能同时属于多对通信组合）。

农夫约翰希望最大化互不干扰的通信对数来确保最佳信息流通。你能计算出最多可以同时建立多少对通信吗？

输入格式

第一行包含 $N$、$A$、$B$。 接下来 $N$ 行每行包含 $n_i$ 和 $d_i$。所有 $d_i$ 均不相同。

输出格式

可同时建立的最大互不干扰通信对数。 注意：由于涉及大整数运算，可能需要使用 64 位整数类型（如C/C++中的 long long）。

4 4 5
17 2
100 0
10 1
200 4

118

提示

解释： ID为 $0$ 的奶牛可与 ID 为 $4$ 奶牛通信（ID 之和为 $4$）。由于共有 $100$ 头 ID $0$ 的奶牛和 $200$ 头 ID $4$ 的奶牛，最多可组成 $100$ 对通信组合。

ID 为 $4$ 的奶牛还可与 ID 为 $1$ 的奶牛通信（ID 之和为$5$）。此时剩余 $100$ 头 ID $4$ 的奶牛和 $10$ 头 ID $1$ 的奶牛可组成 $10$ 对通信组合。

最后，ID 为 $2$ 的奶牛可与其他同 ID 奶牛通信。$17$ 头 ID $2$ 的奶牛最多可组成 $8$ 对通信组合（$\lfloor17/2\rfloor=8$）。

总计 $100+10+8=118$ 对通信组合，可以证明这是最大可能值。

• 测试点 $3\sim4$：$A=B$。
• 测试点 $5\sim7$：$N\le 1000$。
• 测试点 $8\sim12$：无额外限制。