Maximum Clear Square Barn

Farmer John owns an n \(\times\) n farm (\(1 \le n \le 1000\)) which contains \(t\) trees (\(1 \le t \le 10000\)). He wants to build a square barn with its sides parallel to the horizontal and vertical axes. To avoid damaging the trees, the barn must be built on a tree‐free area of the farm. Your task is to compute and output the maximum possible side length of such a square barn that can be built without cutting any trees.

You are given the farm size and the positions of the trees on the farm. The input is formatted as follows:

n t
x1 y1
x2 y2
...
xt yt

where each \( (x_i, y_i) \) represents the position of a tree. The coordinates are 1-indexed. You may assume that the barn can be built only on cells that do not contain trees. It is guaranteed that \( t \ge 1 \).

Example

Input:
8 3
2 2
2 6
6 3

The farm grid for this example (with '.' for empty and '#' for tree) might look like:

      0 1 2 3 4 5 6 7 8
    1 . . . . . . . .
    2 . # . . . # . .
    3 . . . . . . . .
    4 . . . . . . . .
    5 . . . . . . . .
    6 . . # . . . . .
    7 . . . . . . . .
    8 . . . . . . . .

Output:
5

Here, the largest square barn has a side length of \(5\) and can be positioned in one of the lower-right regions of the farm.

inputFormat

The first line contains two integers \(n\) and \(t\), representing the size of the farm and the number of trees respectively. Each of the next \(t\) lines contains two integers \(x\) and \(y\), indicating the row and column (1-indexed) of a tree on the farm.

n t
x1 y1
x2 y2
...
xt yt

outputFormat

Output a single integer: the maximum side length of the square barn that can be built without chopping any trees.

sample

3 1
2 2

1