Problem AQ
Cleaning Robot
A company wishes to purchase a square-shaped cleaning robot to clean a rectangularly shaped room. Some parts of the room are obstructed.
There are different robots of different sizes. Each robot can move horizontally and vertically in the room if no part of the robot intersects an obstruction. They are incapable of changing orientation, so movements are always axis-aligned. Larger robots will get the job done faster, but are more likely to be hindered by obstructions. The robot must always remain fully in the room with no portion extending past the edges of the rectangle.
What is the largest robot the company can buy that will be able to clean all the squares of the room not occupied by obstructions?
Input
The first line of input contains three integers $n$, $m$ ($3 \le n, m$ and $n \cdot m \le 5\cdot 10^6$) and $k$ ($0 \le k < n \cdot m$, $k < 10^6$), where $n$ and $m$ are the dimensions of the room in inches, and $k$ is the number of obstructions.
Each of the next $k$ lines contains two integers $i$ and $j$ ($1 \le i \le n, 1 \le j \le m$). This specifies that the one-inch square at $(i,j)$ is obstructed. All obstructed squares are distinct.
Output
Output a single integer, which is the maximum length of one side of the largest square-shaped robot that could clean the entire room, or $-1$ if no such robot could clean the entire room.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 7 1 8 3 |
2 |
