题目描述

罗恩想在他的 $n\times n$ 的正方形院子里建一个正方形游泳池，但他的院子里有 $T$ 棵树。

你的任务是确定他可以建造的最大的方形游泳池的边长。

输入格式

第一行一个整数 $n$ ，具体意义见题目描述。

第二行一个整数 $T$ ，具体意义见题目描述。

接下来 $T$ 行，每行两个整数 $x,y$ ，表示在 $(x,y)$ 上有一棵树。

输出格式

一行，表示游泳池的最大边长。

5
1
2 4

3

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

7

提示

样例 $1$ 解释：

样例 $2$ 解释：

对于 $20\%$ 的数据：$1\le n\le 50,T=1$

对于 $35\%$ 的数据：$1\le n\le 50,1\le T\le 10$

对于 $25\%$ 的数据：$1\le n\le 5\times 10^5,1\le T\le 10$

对于 $100\%$ 的数据：$1\le n\le 5\times 10^5,1\le T\le 100$