역습

Friberg와 Skog은 컴퓨터 게임 Kontringsattack을 자주 함께 플레이한다. 각 경기에서는 경기 중 얼마나 좋은 성과를 냈는지를 나타내는 점수를 받는다. Skog은 여러 경기에서 Friberg보다 더 많은 점수를 받았다는 이유로 자신이 Kontringsattack에서 Friberg보다 더 뛰어나다고 주장하곤 한다. 이에 Friberg는 한 경기에서 Friberg와 Skog의 점수 차이가 어떤 특정한 수 $K\ge 0$ 이하라면 누가 그 경기에서 더 뛰어났는지 판정할 수 없다고 맞선다. 더 형식적으로 말하면, Friberg가 $F$점, Skog이 $S$점을 받았을 때 $|F - S| \le K$이면 둘은 똑같이 뛰어난 것으로 간주하며, 그렇지 않으면 점수가 더 높은 선수가 더 뛰어나다.

물론 수 $K$는 Friberg가 정한다. 여러 경기와 각 경기에서 Friberg와 Skog이 받은 점수가 주어질 때, Friberg가 더 뛰어난 경기 수와 Skog이 더 뛰어난 경기 수의 차이가 가능한 한 커지도록 Friberg는 $K$의 값을 얼마로 정해야 하는가? 그러한 값이 여러 개라면 가장 작은 값을 구하여라.

채점

여러 테스트 케이스 그룹을 통해 제출한 풀이를 테스트한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한 조건

$1$ |$15$| $N \le 100$ 그리고 $F,S\le 30$

$2$ |$35$| $N \le 1\,000$ 그리고 $F,S\le 1\,000$

$3$ |$50$| 추가 제한 조건이 없다

• 첫 번째 줄에 정수 $N$이 주어진다($1 \le N \le 100\,000$).

• 다음 $N$개의 줄에는 두 정수 $F$, $S$이 주어지며($0 \le F, S \le 1\,000\,000$), 각각 Friberg의 점수와 Skog의 점수이다.

정수 $K$를 한 줄에 출력한다.