냉장 진열대 점검 시간

문제

한 편의점은 냉장 진열대의 점검 일정을 분 단위로 관리한다. 점검 중인 진열대마다 직원 한 명이 필요하므로, 점장은 한 해 동안 동시에 필요한 직원 수가 가장 많은 시각을 알아내려 한다. 각 점검 기록에는 시작 날짜, 시작 시각, 진행 시간이 적혀 있다. 서로 다른 기록은 서로 다른 진열대의 점검을 나타내며, 날짜와 시각이 완전히 같은 기록도 각각 별개의 점검으로 센다. 분석 대상은 윤년인 2028년 전체다. 2028년은 366일이며 2월은 29일까지 있다. 나머지 달의 마지막 날짜는 차례로 1월 31일, 3월 31일, 4월 30일, 5월 31일, 6월 30일, 7월 31일, 8월 31일, 9월 30일, 10월 31일, 11월 30일, 12월 31일이다. 모든 시각은 같은 지역의 시각이고, 하루는 정확히 1440분이다. 별도의 시각 보정은 없다. 시작 시각이 s이고 진행 시간이 L분인 점검은 s부터 시작하는 L개의 분에 직원을 필요로 한다. 즉 시작 시각은 포함하고 종료 시각은 포함하지 않는다. 예를 들어 02월 28일 23시 59분에 시작하여 2분 동안 진행하는 점검은 02월 28일 23시 59분과 02월 29일 00시 00분에 집계된다. 종료와 시작이 같은 시각에 일어나면 종료한 점검은 빠지고 새 점검은 들어간다. 모든 점검은 2028년 안에 시작하고, 늦어도 2029년 01월 01일 00시 00분에 종료한다. 동시에 진행 중인 점검 수의 최댓값과 그 값이 처음 나타나는 날짜 및 시각을 구한다. 기록이 하나도 없다면 필요한 직원 수는 0명이며, 분석 대상의 첫 시각을 답으로 삼는다.

입력

첫째 줄에 점검 기록 수 N이 주어진다. N은 0 이상 12,000 이하의 정수다.
다음 N개 줄에는 날짜 MM-DD, 시각 HH:MM, 진행 시간 L이 공백으로 구분되어 주어진다. 날짜와 시각의 각 구성 요소는 두 자리 십진수다. 날짜는 2028년에 존재하는 날짜이고, HH는 00 이상 23 이하, MM은 00 이상 59 이하다. L은 1 이상 1440 이하의 정수다. 모든 점검의 종료 시각은 2029년 01월 01일 00:00 이하이다. 기록은 시간순으로 정렬되어 있지 않을 수 있다.

출력

첫째 줄에 동시에 진행 중인 점검 수의 최댓값을 정수로 출력한다. 둘째 줄에 그 최댓값이 처음 나타나는 날짜와 시각을 MM-DD HH:MM 형식으로 출력한다. N이 0이면 둘째 줄에 01-01 00:00을 출력한다.

3
02-28 23:59 2
02-29 00:00 3
02-29 00:02 1

2
02-29 00:00

2
12-31 23:58 2
12-31 23:57 1

1
12-31 23:57

0

0
01-01 00:00

출처: Devin.KR 자체 제작