병원 예약표의 가장 긴 빈 시간

문제

병원의 예약 관리 담당자는 연속된 여러 날짜의 예약 자료를 모아 진료실을 비워 둘 수 있는 가장 긴 시간을 찾으려 한다. 관리 대상 기간의 첫 날짜를 1일이라고 부르며, 이후 날짜에는 차례로 번호를 붙인다. 각 날짜는 정확히 24시간이고, 한 시간은 60분이다. 관리 대상 기간은 1일 00:00에 시작하여 D일의 다음 날 00:00에 끝난다. 이 기간에는 날짜가 바뀌는 순간에도 시간이 끊기지 않는다. 예약 자료 하나에는 시작 날짜 d, 시작 시각 HH:MM, 사용 시간 L이 기록되어 있다. 예약은 시작 순간부터 정확히 L분 동안 진료실을 사용한다. 예를 들어 2일 23:50에 시작하여 20분 동안 사용하는 예약은 3일 00:10에 끝난다. 모든 예약은 관리 대상 기간 안에서 시작하고 끝난다. 예약이 끝나는 순간은 사용 시간에 포함되지 않으므로, 어떤 예약이 끝나는 순간 다른 예약이 시작하면 그 사이에는 빈 시간이 없다. 여러 부서가 같은 진료실의 예약 자료를 따로 제출했기 때문에 예약끼리 겹칠 수 있으며, 내용이 완전히 같은 자료가 여러 번 등장할 수도 있다. 겹치는 부분은 한 번만 사용 중인 것으로 본다. 입력에 등장하는 순서는 실제 예약의 시간 순서와 관계없다. 예약이 하나도 없는 경우도 있다. 담당자는 관리 대상 기간 안에서 어떤 예약에도 사용되지 않는 연속된 시간을 찾는다. 빈 시간의 시작과 끝은 모두 분 단위이며, 날짜의 경계를 지나 이어질 수 있다. 가장 긴 빈 시간이 여러 개라면 시작 순간이 가장 이른 것을 선택한다. 선택한 빈 시간의 시작 날짜, 시작 시각, 길이를 출력한다. 길이가 1분 이상인 빈 시간이 전혀 없다면 정해진 표시만 출력한다.

입력

첫째 줄에 관리할 날짜 수 D와 예약 수 N이 공백으로 주어진다. D와 N은 정수이며 1 ≤ D ≤ 365, 0 ≤ N ≤ 10,000이다.
다음 N개 줄에는 정수 d, 문자열 HH:MM, 정수 L이 공백으로 주어진다. 1 ≤ d ≤ D이며 시각은 00:00부터 23:59까지의 유효한 시각으로, 시와 분을 각각 두 자리로 적는다. 1 ≤ L ≤ 1440이다. 시작 순간을 1일 00:00부터 지난 분으로 바꾼 값을 s라고 할 때 s + L ≤ 1440D가 보장된다.

출력

길이가 양수인 빈 시간이 있으면 시작 날짜, HH:MM 형식의 시작 시각, 길이를 분 단위 정수로 한 줄에 공백으로 구분하여 출력한다. 가장 긴 빈 시간이 여러 개면 가장 먼저 시작하는 것을 출력한다. 빈 시간이 전혀 없으면 -1만 출력한다.

1 3
1 12:00 60
1 00:00 120
1 01:00 120

1 13:00 660

1 1
1 00:00 1440

-1

2 0

1 00:00 2880

출처: Devin.KR 자체 제작