Problem Description

Ron wants to build a square swimming pool in his $n \times n$ square yard, but there are $T$ trees in his yard.

Your task is to determine the side length of the largest square swimming pool he can build.

Input Format

The first line contains an integer $n$, as described in the problem statement.

The second line contains an integer $T$, as described in the problem statement.

The next $T$ lines each contain two integers $x, y$, indicating that there is a tree at $(x, y)$.

Output Format

Output one line containing the maximum side length of the swimming pool.

5
1
2 4

3

15
8
4 7
4 1
14 11
10 6
13 4
4 10
10 3
9 14

7

Hint

Explanation for Sample $1$:

Explanation for Sample $2$:

Constraints:

For $20\%$ of the testdata: $1 \le n \le 50, T = 1$.

For $35\%$ of the testdata: $1 \le n \le 50, 1 \le T \le 10$.

For $25\%$ of the testdata: $1 \le n \le 5 \times 10^5, 1 \le T \le 10$.

For $100\%$ of the testdata: $1 \le n \le 5 \times 10^5, 1 \le T \le 100$.

Translated by ChatGPT 5