2737 - 捕鱼达人
题目描述
小 A 设计了一款捕鱼达人的游戏。
游戏在一个方阵中进行，方阵的大小为 10000 \times 10000，鱼儿在方阵中自由的游动，用整数 X,Y 表示某条鱼在方阵中的坐标。
在某个时刻，屏幕的方阵中有 N 条鱼出现了，已知每条鱼所在位置的坐标。作为捕鱼达人的你，可以在屏幕的任意位置撒出一张正方形的网。
请编程求出，如果网中至少能捕获 M 条鱼，那么正方形网的边长，至少有多长？
输入
第 1 行输入两个整数 M,N，中间用空格隔开。
接下来 N 行，每行读入 2 个整数 X_i,Y_i 表示某条鱼在方阵中的坐标。
请注意：可能会出现多条鱼在同一个坐标点的情况，因此读入的 N 条鱼的坐标中，可能会有部分坐标是相同的。
输出
输出一个整数，代表方形网的最小边长。
样例
输入
3 5 1 2 2 3 1 4 4 1 4 3
输出
3
输入
4 8 1 10 8 2 6 5 7 8 2 9 3 6 8 3 10 1
输出
5
输入
5 10 1 2000 2000 2 1 1000 2000 1 2 2000 2000 3 3 1000 1000 1000 1 10000 10000 1
输出
1001
说明
样例 1 解释
样例 1 每条鱼的坐标如下图所示，可以用橙色或者绿色的边长为 3 \times 3 的正方形网，抓住 3 条鱼。
数据范围
对于 10\% 的数据，M=1。
对于 30\% 的数据，1 \le M \le N \le 10。
对于 100\% 的数据，1 \le M \le N \le 500，1 \le X_i,Y_i \le 10000。
标签