소 우리 만들기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

정사각형이 클로버 밭을 C개 이상 덮을 때, 그 정사각형의 한 변 길이 중 가장 작은 값을 구합니다.

난이도: 보통10점 중 5점
유형: 이분 탐색, 누적 합
정답자: 아직 제출이 없습니다

문제

Farmer John은 소들을 위한 우리를 짓고 싶어 한다. 까다로운 소들은 우리가 정사각형이어야 하고, 오후 간식용 클로버 밭을 최소 $C$ 개( $1 \le C \le 500$ ) 포함하기를 원한다. 우리의 변은 X축과 Y축에 평행해야 한다.

FJ의 땅에는 총 $N$ 개( $C \le N \le 500$ )의 클로버 밭이 있다. 각 밭은 $1 \times 1$ 크기의 블록이고, 왼쪽 아래 모서리가 1 이상 10,000 이하의 정수 X, Y 좌표에 놓여 있다. 같은 위치에 클로버 밭이 둘 이상 자랄 수 있으며, 이 경우 입력에 그 위치가 두 번(또는 그 이상) 나타난다. 밭 전체가 우리의 경계 안에 들어가면 우리가 그 밭을 둘러싼다고 한다.

클로버 밭을 $C$ 개 이상 포함하는 가장 작은 정사각형의 한 변 길이를 구하라.

입력

첫 줄에 공백으로 구분된 정수 $C$ 와 $N$ 이 주어진다.

이어지는 $N$ 개의 줄에는 클로버 밭 하나의 X 좌표와 Y 좌표가 공백으로 구분되어 주어진다.

출력

클로버 밭을 $C$ 개 이상 포함하는 가장 작은 정사각형의 한 변 길이를 정수 하나로 한 줄에 출력한다.

예제1

예제 1
입력
```
3 4
1 2
2 1
4 1
5 2
```
예상 출력
```
4
```