Kontringsattack

시간 제한4초메모리 제한1024 MB

요약

|F-S|<=K인 경기를 무승부로 볼 때 프리베리 승리 수에서 스코그 승리 수를 뺀 값이 최대가 되는 가장 작은 K를 구한다.

난이도: 보통10점 중 6점
유형: 정렬, 그리디, 배열, 수학
정답자: 아직 제출이 없습니다

문제

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$ 를 어떤 값으로 정해야 하는가? 그러한 값이 여러 개라면 가장 작은 값을 구하라.

입력

첫 번째 줄에는 정수 $N$ 이 주어진다 ( $1 \le N \le 100\,000$ ).
다음 $N$ 개의 줄에는 두 정수 $F$ , $S$ 가 주어진다 ( $0 \le F, S \le 1\,000\,000$ ). 이는 각각 Friberg의 점수와 Skog의 점수이다.

출력

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

예제3

예제 1
입력
```
3
5 6
6 8
7 2
```
예상 출력
```
2
```
예제 2
입력
```
1
3 5
```
예상 출력
```
2
```
예제 3
입력
```
3
4 6
6 4
3 3
```
예상 출력
```
0
```