You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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)$。

输出格式

一行一个整数表示答案。

3 4
1 2
2 1
4 1
5 2

4

提示

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