Broken Tiles

Time limit0.5sMemory limit512 MB

Summary

Given a rectangle split by a monotone rectilinear curve, find the largest possible minimum side length among rectangles from a rectangular cut of both pieces.

Level: Hard8 of 10
Topics: Binary search, Greedy, Geometry
Solved: No attempts yet

Problem

A rectangular tile fell to the ground and broke into two pieces. Fortunately, the tile broke along a rectilinear curve that is monotone to the sides of the tile, as shown in the left figure below. A rectilinear curve is composed of line segments. A rectilinear curve R is monotone to a straight line or line segment L if every straight line orthogonal to L intersects R at most once.

Since the tiles must be rectangular, we cut each piece further with a cutter into rectangular tiles, using lines through the sides of the piece. We call such a cut a rectangular cut of the pieces. Every rectangular cut partitions the two pieces into rectangles. Among all possible rectangular cuts, we want the one that maximizes the minimum side length of the resulting rectangles.

For example, the left figure above shows an axis-aligned rectangle with side lengths 17 and 11. It is broken into two pieces along the monotone rectilinear curve that connects the points (4,0), (4,4), (11,4), (11,8), (13,8), and (13,11) in order, using line segments. In a rectangular cut, you are allowed to cut each piece along a horizontal line, a vertical line, or both, starting from a corner vertex at (4,4), (11,4), (11,8), or (13,8). The right figure shows a rectangular cut. For the left piece, we choose horizontal lines at (4,4) and (11,8). For the right piece, we choose a horizontal line at (13,8) and a vertical line at (11,4). This cut partitions the two pieces into six rectangles R1, R2, ..., R6. Since R1 and R6 have the minimum side length 3 among the six rectangles, this cut has minimum side length 3. This cut maximizes the minimum side length among all possible rectangular cuts of the broken pieces.

Input

The input starts with a line containing two integers, a and b (1 ≤ a ≤ 100,000, 1 ≤ b ≤ 100,000), where a and b are the x-coordinate and the y-coordinate of the top-right corner of the axis-aligned rectangle whose bottom-left corner is at (0,0). There is no input with a = b = 1. The next line contains one integer n (2 ≤ n ≤ 100,000), the number of points of the monotone rectilinear curve that breaks the rectangle into two pieces. The following n lines each contain two integers, c and d (0 ≤ c ≤ a, 0 ≤ d ≤ b), the x-coordinate and the y-coordinate of the i-th point along the curve. All points are distinct.

Output

Print exactly one line. The line contains the maximum of the minimum side lengths among all possible rectangular cuts.

Examples3

Example 1
Input
```
3 4
2
1 0
1 4
```
Expected output
```
1
```
Example 2
Input
```
4 5
4
4 2
2 2
2 3
0 3
```
Expected output
```
2
```
Example 3
Input
```
17 11
6
4 0
4 4
11 4
11 8
13 8
13 11
```
Expected output
```
3
```