스터디룸 청소 간격

문제

어느 도서관에는 같은 크기의 스터디룸이 K개 있다. 내일 접수된 예약은 N건이며, i번째 예약은 시각 s_i에 입실해서 시각 e_i에 퇴실하는 구간 [s_i, e_i)를 사용한다. 한 방에서 앞 예약의 퇴실 시각과 뒤 예약의 입실 시각이 같아도 되며, 이때는 구간이 겹치지 않는 것으로 본다. 운영팀은 같은 방에서 연달아 사용되는 두 예약 사이에 청소 시간을 최소 g만큼 확보하려고 한다. 즉 같은 방에서 예약 i 바로 다음에 예약 j가 배정된다면 s_j ≥ e_i + g 를 만족해야 한다. 예약의 시각은 바꿀 수 없고, 각 예약은 K개의 방 중 정확히 한 곳에 배정해야 하며 배정 방법은 자유롭게 고를 수 있다. 모든 N건을 위 조건으로 배정할 수 있는 정수 g(g ≥ 0) 중 가장 큰 값을 구하는 프로그램을 작성한다. g = 0 으로도 배정이 불가능하면 -1을 출력한다. 반대로 g를 얼마나 크게 잡아도 배정이 가능하면(방의 수가 예약 수 이상인 경우) INF를 출력한다.

입력

첫 줄에 예약 수 N과 방의 수 K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ 200,000) 다음 N개의 줄에 각각 정수 s_i, e_i가 공백으로 구분되어 주어진다. (0 ≤ s_i < e_i ≤ 1,000,000,000)

출력

조건을 만족하는 g의 최댓값을 한 줄에 출력한다. g = 0 도 불가능하면 -1, 얼마든지 가능하면 INF를 출력한다.

4 2
0 4
1 3
5 8
6 9

2

3 1
0 2
2 5
7 8

0

2 1
0 5
3 4

-1

출처: Devin.KR 자체 제작