회의실 예약 분량 집계

문제

공유 업무 공간의 데이터 담당자는 하루 동안 접수된 회의실 예약 표를 받아 회의실별 예약 분량을 집계한다. 표에는 예약 한 건마다 회의실 코드, 시작 시각, 종료 시각이 들어 있다. 시각은 해당 날짜의 0시부터 지난 분으로 나타내며, 예약 한 건의 분량은 종료 시각에서 시작 시각을 뺀 값이다. 회의실 코드는 길이가 1 이상 3 이하인 영문 대문자 문자열이다. 코드가 정확히 같으면 같은 회의실을 뜻하며, 코드가 다르면 서로 다른 회의실을 뜻한다. 각 데이터 행의 세 값은 쉼표로 구분된다. 쉼표 앞뒤에 공백은 없고 따옴표로 감싼 값도 없다. 첫 번째 행은 열 이름을 나타내는 고정된 헤더이며 예약 건수에 포함하지 않는다. 이 표는 접수된 예약 요청을 보관한 자료이므로 같은 회의실의 예약 시간이 겹칠 수 있다. 이번 집계에서는 실제로 회의실을 사용한 시간이나 겹치는 구간의 길이를 계산하지 않는다. 각 행에 적힌 예약 분량을 그대로 더한다. 모든 값이 같은 행이 여러 번 나와도 각각 별도로 접수된 예약으로 취급하여 모두 더한다. 예약 행의 순서는 집계 결과에 영향을 주지 않는다. 데이터 담당자는 예약 분량의 합이 가장 큰 회의실 하나를 보고하려 한다. 합이 같은 회의실이 여러 개라면 회의실 코드가 사전순으로 가장 앞선 것을 고른다. 사전순은 영문 대문자 A부터 Z까지의 순서를 따르며, 한 코드가 다른 코드의 접두사라면 더 짧은 코드가 앞선다. 예를 들어 A는 AA보다 앞서고, AA는 B보다 앞선다. 표에 등장한 회의실만 후보로 삼는다. 선택한 회의실의 코드와 예약 분량의 합을 구한다. 예약이 한 건도 없어서 후보가 없으면 정해진 빈 결과를 출력한다.

입력

첫째 줄에 예약 건수인 정수 N이 주어진다. 0 ≤ N ≤ 20,000이다.
둘째 줄에 헤더 room,start,end가 주어진다.
다음 N개 줄에 회의실 코드 R, 시작 시각 S, 종료 시각 E가 R,S,E 형식으로 주어진다. R은 길이가 1 이상 3 이하인 영문 대문자 문자열이다. S와 E는 정수이며 0 ≤ S < E ≤ 1,440이다. 정수는 불필요한 앞자리 0 없이 표기한다.

출력

예약 분량의 합이 가장 큰 회의실의 코드와 그 합을 공백으로 구분하여 한 줄에 출력한다. 동점이면 사전순으로 가장 앞선 코드를 출력한다. N = 0이면 NONE 0을 출력한다.

5
room,start,end
B,60,100
A,0,30
B,90,120
A,100,140
C,0,20

A 70

0
room,start,end

NONE 0

3
room,start,end
AA,0,10
A,20,30
AA,0,10

AA 20

출처: Devin.KR 자체 제작