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) 통신 쌍을 만들고자 합니다. 여러분은 한 번에 형성될 수 있는 최대 통신 쌍의 수를 구해야 합니다.

#8416 upload 2 done 1 how_to_reg 1

Compatible Pairs timer 1s memory 1024MB

#8416

Compatible Pairs 1s 1024MB