Desciption

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 <= C <= 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 <= N <= 500) clover fields, each a block of size 1 x 1 and located at with its lower left corner at integer X and Y coordinates each in the range 1..10,000. 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< 500)个草场,来供应她们的午餐.

约翰的土地上共有C<=N<=500)个草场,每个草场在一块1x1的方格内,而且这个方格的 坐标不会超过10000.有时候,会有多个草场在同一个方格内,那他们的坐标就会相同.

告诉约翰,最小的围栏的边长是多少?

Input

Line 1: Two space-separated integers: C and N

Lines 2..N+1: Each line contains two space-separated integers that are the X,Y coordinates of a clover field.

Output

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.

Sample Input

1
2
3
4
5
3 4
1 2
2 1
4 1
5 2

Sample Output

1
4

Hint

Explanation of the sample:

|

|

+———Below is one 4x4 solution (C’s show most of the corral’s area); many others exist.

|CCCC

|CCCC

|CCC

|CC

+———

分析

二分搜索栅栏的边长,每次将边长带入到图中,计算出最多能覆盖到的草场的数量即可
{:.success}

要计算覆盖草场的数量,选定一块草场 $i$ ,将 $x[i]$ 设为覆盖的上边界,得出下边界,在上边界和下边界中二分查找(使用 $ lower_\;bound $)找到左右边界的草场编号范围(当然这需要提前对草场位置排序)

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 10001
#define fr(na,st,ed) for(int na=st;na<=ed;na++)
using namespace std;
int x[maxn],y[maxn];
int id1[maxn],id2[maxn];
int n,c; int l=1,r,mid;
inline bool cmp1(int q,int w){
return x[q]<x[w];
}
inline bool cmp2(int q,int w){
return y[q]<y[w];
}

inline bool check(int size){
int st,ed,k,sum;
fr(i,1,n){
k=1; sum=0;
st=x[id1[i]]; ed=st+size-1;
fr(j,1,n){
while(y[id2[k]]-y[id2[j]]+1<=size && k<=n){
if(st<=x[id2[k]] && x[id2[k]]<=ed) sum++;
k++;
}
if(sum>=c) return true;
if(st<=x[id2[j]] && x[id2[j]]<=ed) sum--;
}
}
return false;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("t3.in","r",stdin);
freopen("t3.out","w",stdout);
#endif
cin>>c>>n;
fr(i,1,n){
cin>>x[i]>>y[i];
r=max(r,max(x[i],y[i]));
id1[i]=id2[i]=i;
}
sort(id1+1,id1+n+1,cmp1);
sort(id2+1,id2+n+1,cmp2);
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
cout<<l;
return 0;
}