P2862 [USACO06JAN] Corral the Cows G

Farmer John 希望为他的奶牛们建立一个畜栏。 这些挑剔的奶牛要求畜栏必须是正方形的，而且至少要包含 $C$ 片三叶草，来当做它们的下午茶。 约翰的土地里一共包含 $N$ 片三叶草，每单位三叶草位于一个 $1\times 1$ 的土地区域内。坐标都为整数，范围在 $1$ 到 $10000$ 以内。 **多片的三叶草可能会位于同一个 $1\times 1$ 的区域内，所以在输入内，同一个区域坐标可能出现多次。** 请你帮 Farmer John 计算一下，在能包含至少 $C$ 片三叶草的情况下，畜栏的最小边长是多少。 $1\le C\le N\le 500$。

第一行两个正整数 $C,N$。 下面 $N$ 行，每行两个整数 $X,Y$，表示某一单位三叶草的位置 $(X,Y)$。

一行一个整数表示答案。

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