사회적 거리두기

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

요약

직선 위에 서로 겹치지 않는 M개의 구간으로 주어진 잔디 위의 서로 다른 정수 점 N개에 소를 배치해 가장 가까운 두 소 사이 거리 D를 최대화하고, 그 최댓값을 출력한다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 그리디, 구간, 정렬
정답자: 아직 제출이 없습니다

문제

고도로 전염성이 강한 소 질병 COWVID-19가 발생한 뒤, Farmer John은 소들의 건강을 걱정하고 있다.

질병의 전파를 막기 위해 Farmer John의 소 $N$ 마리( $2 \leq N \leq 10^5$ )는 "사회적 거리두기"를 실천하며 농장 곳곳에 흩어지기로 했다. 농장은 1차원 수직선 모양이고, 풀이 자라는 서로 겹치지 않는 $M$ 개의 구간( $1 \leq M \leq 10^5$ )이 있다. 소들은 각자 풀로 덮인 서로 다른 정수 점에 자리를 잡아, 가장 가까운 두 소 사이의 거리인 $D$ 를 최대화하려고 한다. 소들이 $D$ 의 최댓값을 구하도록 도와주자.

입력

첫째 줄에 $N$ 과 $M$ 이 주어진다. 다음 $M$ 개의 줄에는 각 구간을 나타내는 두 정수 $a$ 와 $b$ 가 주어진다( $0 \leq a \leq b \leq 10^{18}$ ). 두 구간은 서로 겹치지 않으며 끝점에서도 닿지 않는다. 소가 구간의 끝점에 서 있는 것도 풀 위에 서 있는 것으로 본다.

출력

모든 소 쌍이 $D$ 만큼 떨어져 있도록 하는 $D$ 의 최댓값을 출력한다. $D>0$ 인 해가 존재함이 보장된다.

힌트

소들을 위치 $0$ , $2$ , $4$ , $6$ , $9$ 에 두면 $D=2$ 를 달성할 수 있다.

예제1

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