描述

农夫约翰希望为他的奶牛们建造一个畜栏。这些奶牛非常挑剔，要求畜栏必须是正方形，并且其中至少包含$C$（$1 \leq C \leq 500$）个三叶草田作为下午的零食。畜栏的边缘必须与$X$轴和$Y$轴平行。

约翰的土地上共有$N$（$C \leq N \leq 500$）个三叶草田，每个田块的大小为$1 \times 1$，其左下角位于整数坐标$(X, Y)$上，$X$和$Y$的范围均为$1$到$10,000$。有时多个三叶草田会生长在同一位置；这样的位置会在输入中出现两次（或更多次）。如果一个田块完全位于畜栏的边界内，则认为该田块被畜栏包围。

请帮助约翰计算包含至少$C$个三叶草田的最小正方形的边长。

输入

第1行：两个用空格分隔的整数$C$和$N$

第2行到第$N+1$行：每行包含两个用空格分隔的整数，表示一个三叶草田的$X$和$Y$坐标。

输出

第1行：一个整数，表示包含至少$C$个三叶草田的最小正方形的边长。

输入样例 1

3 4
1 2
2 1
4 1
5 2

输出样例 1

4

提示

样例解释：

|* *

| * *

+------

以下是一个$4 \times 4$的解决方案（C表示畜栏的大部分区域）；还存在其他多种方案。
|CCCC

|CCCC

|CCC

|CC

+------

来源

USACO 2006年1月黄金组