학원 공용 단말기 예약 점검

문제

한 학원은 여러 강의실에서 함께 사용하는 실습용 단말기 K대를 운영한다. 수업 담당자는 실습에 필요한 시간 구간을 예약 시스템에 등록한다. 예약 하나는 그 구간 내내 단말기 한 대를 사용한다는 뜻이다. 단말기는 모두 같은 기능을 제공하므로 어떤 기기를 배정받는지는 중요하지 않다. 다만 같은 시각에 사용 중인 예약 수가 단말기 수보다 많아지면 모든 예약을 동시에 지원할 수 없다. 백엔드 담당자는 아직 기기를 배정하지 않은 예약 목록을 받아 충돌 여부를 점검하려 한다. 예약에는 시작 시각 s와 종료 시각 e가 기록되어 있다. 시각은 하루의 특정 기준점부터 지난 시간을 나타내는 정수다. 예약은 s 이상 e 미만인 시각에 활성 상태다. 따라서 시각 e에 끝나는 예약이 사용하던 단말기는 바로 그 시각에 시작하는 다른 예약에 배정할 수 있다. 시작 시각과 종료 시각이 같은 예약은 입력으로 주어지지 않는다. 같은 시각에 여러 예약이 시작하거나 끝날 수 있다. 이때는 그 시각에 종료되는 예약을 모두 제외하고, 그 시각에 시작하는 예약을 모두 포함한 뒤 활성 예약 수를 판단한다. 처리 도중 잠시 계산된 수치는 충돌 판정에 사용하지 않는다. 입력에 똑같은 구간이 여러 번 등장해도 각각 별개의 예약이며, 예약을 합치거나 취소하지 않는다. 모든 예약을 함께 반영했을 때 활성 예약 수가 K를 초과하는 시각이 있는지 구한다. 그런 시각이 있다면 가장 이른 시각과 그 시각의 활성 예약 수를 출력한다. 단말기 수와 활성 예약 수가 같으면 충돌이 아니다. 모든 시각에서 단말기가 충분하다면 정해진 문자열을 출력한다. 점검 결과에 따라 예약 목록을 수정할 필요는 없다.

입력

첫째 줄에 예약 수 N과 단말기 수 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ N ≤ 20,000, 1 ≤ K ≤ N이다.
다음 N개 줄에 예약의 시작 시각 s와 종료 시각 e가 공백으로 구분되어 주어진다. s와 e는 정수이며 0 ≤ s < e ≤ 1,000,000이다.
예약은 시간순으로 주어지지 않을 수 있다.

출력

충돌이 발생하면 가장 이른 충돌 시각 T와 시각 T의 활성 예약 수 C를 공백으로 구분하여 한 줄에 출력한다. 충돌이 전혀 발생하지 않으면 OK를 출력한다.

5 2
2 7
4 9
7 10
6 8
10 12

6 3

4 2
0 3
0 3
3 6
3 6

OK

4 1
5 9
5 8
5 7
0 5

5 3

출처: Devin.KR 자체 제작