Cricket Field

Time limit2sMemory limit128 MB

Summary

Given up to 100 tree points in a W by H rectangle, find the largest axis-aligned square inside the park with no tree strictly inside it.

Level: Medium6 of 10
Topics: Geometry, Brute force, Sorting
Solved: No attempts yet

Problem

A greedy King orders his Architect to build a square cricket field inside the royal park. The King refuses to let a single tree be cut down or newly planted, yet still demands the largest possible field. Help the Architect find it.

The park is a rectangle on flat ground whose sides are aligned with the coordinate axes, and the cricket field is an axis-aligned square. In the Architect's coordinate system the park's south-western corner is at $(0, 0)$ and its north-eastern corner is at $(W, H)$ , where $W$ and $H$ are the park's width and height in feet.

Tree diameters may be ignored, so each tree is a single point. No tree may lie strictly inside the field, but a tree may lie on the field's border. The field must lie entirely within the park, though it may touch the park's border.

Find the maximum possible side length of the cricket field.

Input

The first line contains three integers $N$ , $W$ , and $H$ ( $0 \le N \le 100$ , $1 \le W, H \le 10000$ ): the number of trees, and the park's width and height in feet.

Each of the next $N$ lines contains two integers $X_i$ and $Y_i$ ( $0 \le X_i \le W$ , $0 \le Y_i \le H$ ), the coordinates of the $i$ -th tree. All trees are at distinct coordinates.

Output

Print a single integer $L$ : the maximum possible side length of a square cricket field that fits inside the park and has no tree strictly in its interior.

Examples3

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