给定一个 N×N的方格矩阵。

左上角方格坐标为 (1,1)，右下角方格坐标为 (N,N)。

有 T 个方格内有树，这些方格的具体坐标已知。

我们希望建立一个正方形的泳池。

你的任务是找到一个尽可能大的正方形子矩阵，要求子矩阵内没有包含树的方格。

输出满足条件的子矩阵的最大可能边长。

输入格式

第一行包含整数 N。

第二行包含整数 T。

接下来 T 行，每行包含两个整数 r,c，表示方格 (r,c) 内有树。

输入保证，这 T 个方格坐标两两不同。

输出格式

一个整数，表示满足条件的子矩阵的最大可能边长。

数据范围

$2≤N≤5×10^5$, 1≤T≤100, $T<N^2$, 1≤r,c≤N

输入样例1：

5
1
2 4

输出样例2：

3

样例2解释

样例矩阵以及最大泳池示意图如下所示：

输入样例2：

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

输出样例2：

7

样例2解释

样例矩阵以及最大泳池示意图如下所示：