Ron wants to build a square pool in his square $N\times N$ yard, but his yard contains $T$ trees. Your job is to determine the side length of the largest square pool he can build.

The first line of input will be an integer $N$ with $N≥2$. 

The second line will be the positive integer $T$ where $T<N^2$. 

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 $G$, 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 one line containing $M$ which is the largest positive integer such that some $N$-by-$N$ square contained entirely in Ron's yard does not contain any of the $T$ trees.

$N \leq 500,000$
$T \leq 100$

3

A picture of the yard is below. The location of the tree is marked by tree and one of several 3-by-3 squares that do not contain the tree is highlighted. All larger squares contain a tree.

7

A picture of the yard is below. The location of each tree is marked by tree and one of several 7-by-7 squares that do not contain a tree is highlighted. All larger squares contain a tree.