Kontringsattack

Time limit4sMemory limit1024 MB

Summary

Choose the smallest K so that counting matches with |F-S|<=K as ties maximizes Friberg's wins minus Skog's wins.

Level: Medium6 of 10
Topics: Sorting, Greedy, Array, Math
Solved: No attempts yet

Problem

Friberg and Skog often play the computer game Kontringsattack together. In each match, a score is awarded that shows how well the player performed during the match. Sometimes Skog claims he is better than Friberg at Kontringsattack, because he scored more points than Friberg in a number of matches. Friberg counters by claiming that if the difference between Friberg's and Skog's scores in a match is less than or equal to some number $K\ge 0$ , then it is impossible to determine who was better in that match. More formally: if Friberg scored $F$ points and Skog scored $S$ points, then they are considered equally good when $|F - S| \le K$ , otherwise the player with the higher score is better.

Of course, it is Friberg who decides the number $K$ . Given a number of matches and Friberg's and Skog's scores in them, what value should Friberg set for $K$ so that the difference between the number of matches where Friberg is better and the number of matches where Skog is better becomes as large as possible? If there are several such values, find the smallest one.

Input

The first line contains an integer $N$ ( $1 \le N \le 100\,000$ ).
The following $N$ lines contain two integers $F$ , $S$ ( $0 \le F, S \le 1\,000\,000$ ), Friberg's score and Skog's score respectively.

Output

One line with the integer $K$ .

Examples3

Example 1
Input
```
3
5 6
6 8
7 2
```
Expected output
```
2
```
Example 2
Input
```
1
3 5
```
Expected output
```
2
```
Example 3
Input
```
3
4 6
6 4
3 3
```
Expected output
```
0
```