Square Pool

Interview

Time limit1sMemory limit1024 MB

Summary

Given an N by N yard with T tree cells, find the side length of the largest axis-aligned square that contains no tree.

Level: Medium6 of 10
Topics: Binary search, Prefix sum, Array, Brute force
Solved: No attempts yet

Problem

Ron wants to build a square pool in his square N-by-N yard, but his yard contains T trees. Determine the side length of the largest square pool he can build.

Input

The first line of input will be an integer N with N ≥ 2. The second line will be the positive integer T where T < N2. The remaining input will be T lines, each representing the location of a single tree. The location is given by two positive integers, R and then C, separated by a single space. Each tree is located at row R and column C where rows are numbered from top to bottom from 1 to N and columns are numbered from left to right from 1 to N. No two trees are at the same location.

Output

Output one line containing M which is the largest positive integer such that some M-by-M square contained entirely in Ron's yard does not contain any of the T trees.

Examples2

Example 1
Input
```
5
1
2 4
```
Expected output
```
3
```

Example 2

Input

Expected output