페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8416

Compatible Pairs 1s 1024MB

문제

JOI 나라의 소들은 평범한 농장동물들이 아닙니다. 이들은 은밀한 소 정보 네트워크의 일원으로, 각 소는 엘리트 소 암호학자들에 의해 신중하게 할당된 ID 번호를 지니고 있습니다. 그러나 Farmer John의 다소 무계획한 태깅 시스템 때문에, 몇몇 소들은 같은 ID를 갖게 되었습니다.

Farmer John은 서로 다른 ID가 총 N개 있으며 (1\le N\le 2\cdot 10^5), 각각의 고유 ID d_i에 대하여 (0\le d_i\le 10^9) 그 ID를 가진 소가 n_i마리 존재함을 확인했습니다 (1\le n_i\le 10^9).

소들은 오직 쌍으로만 대화할 수 있으며, 그들의 비밀 암호 통신 방식에는 한 가지 엄격한 규칙이 있습니다: 두 소가 서로 대화하려면 서로 다른 소여야 하며, 두 소의 ID 숫자의 합이 반드시 A 또는 B가 되어야 합니다 (0\le A\le B\le 2\cdot 10^9). 한 소는 한 번에 단 한 개의 대화에만 참여할 수 있습니다 (즉, 한 소가 여러 쌍에 동시에 포함될 수 없습니다).

Farmer John은 정보 전달의 원활함을 위해 동시에 가능한 한 많은 서로 겹치지 않는 (disjoint) 통신 쌍을 만들고자 합니다. 여러분은 한 번에 형성될 수 있는 최대 통신 쌍의 수를 구해야 합니다.


입력

첫 번째 줄에 정수 N, A, B가 주어집니다.

이후 N개의 줄 각각에 두 정수 n_i와 d_i가 공백으로 구분되어 주어지며, 모든 d_i는 서로 다릅니다.


출력

출력은 표준 출력에 한 줄로 나타내며, 동시에 형성될 수 있는 최대 통신 쌍의 수를 출력합니다.


예제 #1

4 4 5
17 2
100 0
10 1
200 4
118

ID가 0인 소는 ID가 4인 소와 대화할 수 있습니다. 왜냐하면 두 소의 ID 합이 0 + 4 = 4가 되기 때문입니다. ID가 0인 소는 총 100마리, ID가 4인 소는 총 200마리 있으므로 이 두 그룹을 연결해 최대 100쌍의 통신이 가능합니다.

또한, ID가 4인 소는 ID가 1인 소와 대화할 수 있는데 (4 + 1 = 5), ID가 1인 소는 10마리 있고 남은 ID가 4인 소는 100마리 있으므로 추가로 10쌍의 통신이 가능합니다.

마지막으로, ID가 2인 소들은 자기 자신끼리 통신할 수 있습니다. ID가 2인 소는 총 17마리 있으므로 최대 8쌍의 통신이 가능합니다.

총 통신 쌍의 수는 100 + 10 + 8 = 118쌍입니다.


예제 #2

4 4 5
100 0
10 1
100 3
20 4
30

ID가 0와 4를 쌍으로 연결하면 20쌍, ID가 1과 3을 연결하면 10쌍의 통신이 가능하여 총 20 + 10 = 30쌍이 됩니다.


출처

USACO 2025 US Open Silver
로그인해야 코드를 작성할 수 있어요.