우체국의 집중 접수 시간

문제

한 우체국에서는 접수 창구에 일이 얼마나 몰리는지 알아보기 위해 우편물 접수 기록을 분석한다. 각 기록에는 접수한 날짜와 시각, 그리고 해당 접수를 처리하는 데 필요한 작업량이 적혀 있다. 기록은 모두 2025년에 발생했으며 날짜와 시각이 빠른 순서로 주어진다. 서로 다른 두 기록의 접수 시각은 같지 않다. 분석 담당자는 양의 정수 L을 정하고, 각 접수 시각을 끝 시각으로 하는 집중 구간을 조사한다. 끝 시각이 T인 집중 구간에는 T보다 L분 전인 시각을 초과하고 T 이하인 시각에 접수된 기록이 들어간다. 따라서 정확히 L분 전에 접수된 기록은 포함하지 않고, 끝 시각에 접수된 기록은 포함한다. 집중 구간의 작업량은 그 구간에 포함된 모든 기록의 작업량을 더한 값이다. 기록 한 건이 여러 집중 구간에 포함되어도 된다. 예를 들어 L이 60이고 끝 시각이 03-02 00:20이면, 전날인 03-01 23:20을 초과하고 03-02 00:20 이하인 접수 기록의 작업량을 더한다. 날짜가 바뀌어도 시간은 끊김 없이 이어진다. 구간의 시작이 2025년 이전으로 넘어가면 입력에 있는 기록만 계산한다. 입력에 나타나지 않은 접수는 없다고 본다. 조사할 끝 시각은 입력에 주어진 접수 시각으로 한정한다. 작업량이 가장 큰 집중 구간을 찾아 그 작업량과 끝 날짜 및 시각을 출력해야 한다. 최대 작업량이 같은 구간이 여러 개면 끝 시각이 가장 빠른 구간을 고른다. 접수 기록은 적어도 하나이므로 선택할 구간은 항상 존재한다. 2025년은 윤년이 아니며, 날짜와 시각은 모두 같은 지역의 시계를 기준으로 한다. 일광 절약 시간이나 시차 변경은 없다.

입력

첫째 줄에 정수 N과 L이 공백으로 주어진다. N은 접수 기록 수이며 1 ≤ N ≤ 20,000이다. L은 구간 길이이며 1 ≤ L ≤ 525,600이다.
다음 N개 줄에 날짜 D, 시각 H, 정수 작업량 W가 공백으로 주어진다. D는 2025년에 실제로 존재하는 날짜를 MM-DD 형식으로 나타낸다. H는 00:00부터 23:59까지의 시각을 HH:MM 형식으로 나타낸다. 월, 일, 시, 분은 각각 두 자리로 주어진다. 1 ≤ W ≤ 9이다. 기록은 날짜와 시각을 합친 순서로 엄격히 증가한다.

출력

첫째 줄에 최대 작업량, 선택한 끝 날짜, 선택한 끝 시각을 공백으로 구분하여 출력한다. 날짜는 MM-DD, 시각은 HH:MM 형식을 유지한다.

5 60
01-31 23:30 4
02-01 00:00 3
02-01 00:30 8
02-01 00:45 2
02-01 01:30 1

13 02-01 00:45

3 1
12-31 23:57 5
12-31 23:58 5
12-31 23:59 2

5 12-31 23:57

출처: Devin.KR 자체 제작