该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

0x00基本算法（练习）6：赶牛入圈

P2862 [USACO06JAN] Corral the Cows G

题目描述

给出 边长 $10000$ 的大正方形平面，平面分成 $10000$ 行， $10000$ 列，故有 $10000 \times 10000$ 个 $1 \times 1$ 的格子。

平面上有 $n$ 个人，给出每个人的位置 （$X \ , \ Y$） ，表示人在第 $X$ 行第 $Y$ 列的格子，可能有多个人的位置相同。

在平面上圈出边长为 $L$ 的正方形，使得正方形内至少包含 $C$ 个人。求 $L$ 的最小值。

输入格式

第一行两个正整数 $C \ \ N \ (1 \le C \le N \le 500)$。

下面 $N$ 行，每行两个整数 $X \ \ Y \ \ ( 1 \le X,Y \le 10000)$ 。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

3 4
1 2
2 1
4 1
5 2

输出 #1

4

说明/提示

样例的一个最优解是，将正方形的左下角设为 $(1,1)$，右上角为 $(4,4)$。