마감 전에 가장 많이 팔린 메뉴

문제

카페의 운영 담당자는 주문 로그에서 특정 시간대의 판매량을 집계하려 한다. 주문 시스템은 주문이 접수될 때마다 시각, 메뉴 코드, 판매 수량을 한 줄로 남긴다. 모든 로그는 같은 날에 생성되었지만, 서버에서 모으는 과정에서 순서가 섞일 수 있다. 따라서 입력에 먼저 나온 로그가 더 이른 주문이라는 보장은 없다. 집계 시작 시각 S와 종료 시각 E가 주어진다. 시각은 모두 24시간제 HH:MM 형식이며, 시와 분을 각각 두 자리로 표시한다. S 이상 E 미만인 시각에 접수된 로그만 집계한다. 시작 시각과 정확히 같은 로그는 포함하고, 종료 시각과 정확히 같은 로그는 포함하지 않는다. S는 E보다 이르며 집계 구간은 자정을 넘지 않는다. 메뉴 코드는 소문자 알파벳으로 이루어진 문자열이다. 같은 메뉴 코드가 여러 로그에 등장하면 해당 로그들의 판매 수량을 모두 더한다. 로그의 내용이 완전히 같더라도 서로 다른 주문을 나타내므로 각각 더해야 한다. 집계 구간 밖에 있는 로그의 수량은 어떤 메뉴에도 더하지 않는다. 운영 담당자가 필요한 결과는 집계 구간에서 판매 수량의 합이 가장 큰 메뉴 하나와 그 수량이다. 수량의 합이 같은 메뉴가 여러 개라면 메뉴 코드를 사전순으로 비교하여 가장 앞선 메뉴를 선택한다. 사전순은 첫 번째로 다른 문자의 알파벳 순서로 결정하며, 한 문자열이 다른 문자열의 접두사이면 짧은 문자열이 앞선다. 판매 수량은 항상 양의 정수이므로, 집계에 포함된 로그가 하나라도 있으면 선택할 메뉴가 존재한다. 집계 구간에 포함되는 로그가 하나도 없으면 별도로 정해진 빈 결과를 출력한다. 로그를 시간순으로 다시 출력하거나 집계에 등장한 모든 메뉴를 출력할 필요는 없다. 주어진 로그를 처리하여 운영 담당자가 확인할 최종 결과를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 15,000)
둘째 줄에 시작 시각 S와 종료 시각 E가 공백으로 구분되어 주어진다.
다음 N개 줄에 시각 T, 메뉴 코드 C, 정수 Q가 공백으로 구분되어 주어진다.
S, E, T는 00:00부터 23:59까지의 유효한 HH:MM 형식이고 S < E이다. C는 길이 1 이상 8 이하의 소문자 알파벳 문자열이다. 1 ≤ Q ≤ 99이다.

출력

집계 구간에서 판매 수량의 합이 가장 큰 메뉴 코드와 그 합을 공백으로 구분하여 한 줄에 출력한다. 동점이면 메뉴 코드가 사전순으로 가장 앞선 것을 출력한다. 집계에 포함된 로그가 없으면 NONE 0을 출력한다.

6
09:00 11:00
10:20 latte 3
08:59 tea 9
09:00 tea 2
10:50 tea 1
11:00 latte 8
10:20 latte 3

latte 6

3
12:00 13:00
12:10 tea 4
12:20 cocoa 4
13:00 cocoa 9

cocoa 4

2
15:00 16:00
14:59 tea 1
16:00 tea 2

NONE 0

출처: Devin.KR 자체 제작