题目描述

Farmer John wishes to build a corral for his cows. Being finicky beasts, they demand that the corral be square and that the corral contain at least $c \ (1 \leq c \leq 500)$ clover fields for afternoon treats. The corral's edges must be parallel to the $x,y$ axes. FJ's land contains a total of $n \ (c \leq n \leq 500)$ clover fields, each a block of size $1 \times 1$ and located at with its lower left corner at integer $x$ and $y$ coordinates each in the range $1 \ldots 10^4$. Sometimes more than one clover field grows at the same location;such a field would have its location appear twice (or more) in the input. A corral surrounds a clover field if the field is entirely located inside the corral's borders. Help FJ by telling him the side length of the smallest square containing $C$ clover fields.

约翰打算建一个围栏来圈养他的奶牛。作为最挑剔的兽类，奶牛们要求这个围栏必须是正方形的，而且围栏里至少要有 $c$ 个草场，来供应她们的午餐。约翰的土地上共有 $n$ 个草场，每个草场在一块 $1\times1$ 的方格内，而且这个方格的坐标不会超过 $10^4$。有时候，会有多个草场在同一个方格内，那他们的坐标就会相同。告诉约翰，最小的围栏的边长是多少？

输入格式

• Line $1$：Two space-separated integers：$c$ and $n$.
• Lines $2 \ldots n+1$：Each line contains two space-separated integers that are the $x,y$ coordinates of a clover field.

第 $1$ 行输入 $c$ 和 $n$，接下来 $n$ 行每行输入一对整数，表示一个草场所在方格的坐标。

输出格式

• Line $1$：A single line with a single integer that is length of one edge of the minimum size square that contains at least $c$ clover fields.

输出最小边长。

3 4
1 2
2 1
4 1
5 2

4

样例说明

Below is one $4\times 4$ solution( C's show most of the corral's area ) ; many others exist.

|CCCC
|CCCC
|*CCC*
|C*C*
+------

数据规模与约定

对于 $100\%$ 的数据，$1 \leq c \leq 500$，$c \leq n \leq 500$。

题目来源

Gold