시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 64 MB 86 40 39 65.000%

문제

몇 달 전에 첵스 나라에서 대통령 선거를 했다. 대통령 선거에는 체키와 차카 두 후보가 출마했는데, 체키는 이 나라의 주식인 첵스에 초콜릿을 더 넣어서 만들겠다는 공약을 내밀었고, 차카는 첵스를 파맛으로 만들겠다는 공약을 내밀었다.

첵스 나라에서는 선거를 중복 투표로 진행한다. 유권자 한 명은 두 후보에게 도합 100,000개 이하의 표를 던진다. 선거가 끝나면 더 많은 표를 받은 후보가 당선된다. 만약 받은 표의 개수가 같다면 후보 중에서 어느 누구도 당선되지 않는다.

첵스 나라의 주민들은 차카의 신선한 공약을 보고 차카에게 더 많은 표를 던졌지만, 실제로는 체키가 당선되었다. 한 달 후, 선거관리위원회 직원의 내부고발에 의해 부정선거 의혹이 일어났다. 내부고발에 의하면, 다음과 같은 방법으로 일부 유권자들의 표를 모두 무효표로 처리했다고 한다.

  • 한 후보에게 X표 이상을 투표했거나 총 Y표 이상 투표한 유권자들의 표를 무효표 처리한다. (단, X, Y는 1 이상 100,000 이하의 정해진 정수이다.)

내부고발자도 X와 Y가 무엇인지는 잘 모르기 때문에 프로그래머인 당신이 X, Y를 유추해야 한다. X와 Y의 값으로 가능한 경우의 수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 투표를 한 유권자의 수 N이 주어진다. (2 ≤ N ≤ 1,000)

두 번째 줄부터 N개의 줄에는 각 유권자가 체키와 차카에게 던진 표의 개수 Ai, Bi가 주어진다. 이때 Bi의 합이 Ai의 합보다 큰 데이터만 주어진다. (0 ≤ Ai, Bi 이고 1 ≤ Ai + Bi ≤ 100,000)

출력

X와 Y의 값으로 가능한 경우의 수를 출력한다.

예제 입력

3
2 6
5 3
6 5

예제 출력

99992

힌트

X = 6, 9 ≤ Y ≤ 100,000일 때만 체키가 당선된다.

출처

Contest > FunctionCup > FunctionCup 2016 C번