공유 자전거의 혼잡한 분

문제

공유 자전거 운영팀은 여러 날에 걸친 대여 기록을 모아 서비스의 혼잡도를 확인하려 한다. 분석 기간은 1일 00:00부터 D일의 다음 날 00:00 직전까지다. 이 기간에는 정확히 D × 1,440개의 분이 있다. 달력의 월과 연도는 사용하지 않고, 날짜를 1일부터 차례대로 번호 붙인다. 모든 날은 정확히 24시간이며 시간 변경은 없다. 각 대여 기록에는 대여를 시작한 날짜와 시각, 반납한 날짜와 시각이 들어 있다. 모든 시각은 분 단위로 주어진다. 한 기록의 자전거는 시작 시각에 해당하는 분부터 사용 중이고, 반납 시각에 해당하는 분부터는 사용 중이 아니다. 예를 들어 1일 09:12에 대여하여 같은 날 09:15에 반납했다면 09:12, 09:13, 09:14의 세 분에만 사용 중인 자전거 한 대로 센다. 자정을 넘는 기록도 같은 규칙을 적용한다. 각 기록은 서로 다른 대여 한 건을 나타낸다. 시작 시각과 반납 시각이 모두 같은 기록이 여러 개 있어도 각각 별도의 자전거로 계산한다. 또한 어떤 자전거의 반납 시각과 다른 자전거의 시작 시각이 같다면, 그 분에는 반납된 자전거를 제외하고 새로 대여된 자전거를 포함한다. 운영팀이 필요한 값은 분석 기간 중 동시에 사용 중인 자전거 수의 최댓값, 그 최댓값이 처음 나타난 날짜와 시각, 그리고 그 최댓값이 나타난 분의 총개수다. 최댓값이 나타나는 구간이 떨어져 있어도 모든 분을 합산한다. 입력 기록이 없는 경우에도 분석 기간의 모든 분을 살핀다. 이 경우 최댓값은 0이며, 처음 나타난 시각은 1일 00:00이고 해당 분의 총개수는 D × 1,440이다. 대여 기록을 분 단위 시간축에 반영하여 운영팀의 세 가지 분석 결과를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 D와 N이 주어진다. 1 ≤ D ≤ 90이고 0 ≤ N ≤ 15,000이다.
이후 N개의 줄에 시작 날짜 s, 시작 시각 a, 반납 날짜 e, 반납 시각 b가 공백으로 주어진다. 날짜는 정수이고 시각은 HH:MM 형식이다. HH는 00부터 23까지, MM은 00부터 59까지이며 각각 두 자리다.
1 ≤ s ≤ D이고 1 ≤ e ≤ D+1이다. e가 D+1이면 b는 반드시 00:00이다. 각 기록의 시작 시각은 반납 시각보다 엄격히 이르다. 모든 기록은 분석 기간 안에서 시작하며 기간이 끝나는 시각까지 반납된다. 기록의 입력 순서에는 제한이 없다.

출력

첫째 줄에 동시에 사용 중인 자전거 수의 최댓값을 정수로 출력한다. 둘째 줄에 그 최댓값이 처음 나타난 날짜와 시각을 공백으로 구분하여 출력한다. 날짜는 앞에 0을 붙이지 않은 정수로, 시각은 HH:MM 형식으로 출력한다. 셋째 줄에 최댓값이 나타난 분의 총개수를 정수로 출력한다.

1 3
1 08:00 1 08:03
1 08:02 1 08:05
1 08:04 1 08:06

2
1 08:02
2

2 2
1 23:58 2 00:02
2 00:00 2 00:01

2
2 00:00
1

2 0

0
1 00:00
2880

출처: Devin.KR 자체 제작