Lee Dongho's Truck

Time limit2sMemory limit128 MB

Summary

Given pillar coordinates in a square warehouse, find the widest integer-width straight lane from west to east that touches no pillar or wall.

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

Problem

Lee Dongho wants to store his paintings in a square warehouse whose side length is 200 meters. The north and south sides of the warehouse are walls, while the entire west and east sides are sliding doors, so a truck can enter from the west and leave through the east. A truck's width is an integer number of meters, and inside the warehouse it must move in a straight line without changing direction. The roof is high enough that height never matters.

Inside the warehouse there are pillars supporting the roof. Each pillar is treated as a point with no size. The truck may not pass through or touch any pillar, nor may it pass through or touch the north or south wall.

Given the positions of the pillars, find the maximum possible width of a truck that can pass through the warehouse.

Input

The first line contains the number of pillars N. N is a nonnegative integer not greater than 50.

Each of the next N lines contains the position of one pillar as two integers. The first integer is the distance from the east wall, and the second integer is the distance from the north wall. Both integers are between 0 and 200, inclusive.

Output

Print one integer: the maximum width of a truck that can pass through the warehouse.

Examples3

Example 1
Input
```
3
100 60
100 140
120 180
```
Expected output
```
79
```
Example 2
Input
```
1
0 200
```
Expected output
```
199
```
Example 3
Input
```
2
100 60
120 140
```
Expected output
```
82
```