Appointments

Interview

Time limit2sMemory limit128 MB

Summary

Given N pairs of appointment and arrival times, find how many integer shifts T minimize the total waiting time, which reduces to counting optimal medians of the differences.

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

Problem

N wizards made appointments with Muggles to better understand Muggle culture. Each wizard will meet exactly one Muggle. Because a wizard may arrive earlier or later than the appointment time, they want to adjust every appointment by the same integer T.

The waiting time for one appointment is the time that the person who arrives first waits until the other person arrives. The original appointment times are A_1, A_2, ..., A_N, and the wizards' arrival times are B_1, B_2, ..., B_N. If every appointment time is shifted by T, the total waiting time becomes the sum of |A_i + T - B_i|.

Find the number of distinct integers T that minimize the total waiting time.

Input

The first line contains N.

Each of the next N lines contains two integers A_i and B_i.

Output

Print the number of distinct integers T that minimize the total waiting time.

Constraints

1 <= N <= 50
1 <= A_i, B_i <= 10^9

Examples5

Example 1
Input
```
1
10 9
```
Expected output
```
1
```
Example 2
Input
```
2
20 18
30 25
```
Expected output
```
4
```
Example 3
Input
```
2
10 11
20 17
```
Expected output
```
5
```
Example 4
Input
```
3
10 13
20 15
30 34
```
Expected output
```
1
```
Example 5
Input
```
4
10 14
20 24
30 39
40 37
```
Expected output
```
1
```