시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 40 13 10 30.303%

문제

CTP대학교 신입생 청원이는 최대한 많은 시간 동안 교수님들의 수업을 강의실에서 들어보고 싶은 로망이 있었다. 그래서 청원이는 우선 오늘 하루 동안의 CTP대학교의 시간표를 확인하고 최대한 많은 시간 동안 강의를 듣고자 한다. 청원이가 확인한 시간표에는 오늘 수강할 수 있는 $N$개의 강의와 $M$개의 강의실 이동 시간 목록에 대한 정보가 적혀 있다. 각 강의는 이름, 시작 시간 그리고 끝나는 시간이 적혀있고, 강의실 이동 시간 목록에는 서로 다른 두 강의실의 이름과 둘 사이의 이동 소요 시간이 적혀 있다. 모든 강의는 서로 다른 강의실에서 열리지만, 시간이 겹치는 것들이 존재한다. 강의실은 강의 시작 시간, 끝나는 시간에 상관없이 들어가고 나올 수 있으며 강의실에 지각해도 해당 강의의 남은 강의 시간에 대해서 강의를 들을 수 있다. 청원이는 강의 시작 시간이 가장 빠른 강의실에 해당 강의 시작 전에 미리 앉아있다. 단, 시작 시간이 같은 강의가 존재한다면, 이름이 사전 순으로 빠른 강의실에 앉아있다. 청원이는 강의 시간 계산을 깔끔하게 하기 위해서 분 단위로만 강의실을 이동한다. 예를 들어, 5시 10분부터 5시 20분까지 강의가 진행중인 강의실에 있었다면 10분 동안 강의를 들은 것이다. 청원이는 강의실을 이동할 때, 이동하고자 하는 강의실까지 이동시간을 알고있는 경우에만 이동할 수 있다. 단, 다른 강의실을 거쳐 가는 것은 가능하다. 오늘 하루 청원이가 최대한 많은 시간의 강의를 들을 수 있도록 도와주자.

입력

첫째 줄에는 청원이가 오늘 하루 동안 듣고 싶은 강의의 개수 $N$, 청원이가 알고 있는 강의실 이동 시간 소요 목록의 개수$M$이 공백으로 구분되어 주어진다.

그 다음 줄 부터 $N$개의 줄에 대해서 강의 이름 $S$, 시작시간 $X$, 끝나는 시간 $Y$가 공백으로 구분되어 주어진다.

$X$와 $Y$는 각각 HH:mm 형태로 주어진다. (오전 3시 3분인 경우 03:03으로 주어진다, 오후 11시 11분인 경우 23:11으로 주어진다.)

그 다음 줄 부터 $M$개의 줄에 대해서 강의 이름 $A$, 강의 이름 $B$, $A$ 와 $B$ 강의실 이동 간 소요되는 시간 $Z$가 공백으로 구분되어 주어진다.

$Z$는 $X$,$Y$ 양방향에 대한 이동시간 정보이다.

출력

청원이가 오늘 하루 들을 수 있는 최대한의 강의 시간의 총 시간을 HH:mm 형태로 출력한다.

(예를 들어, 최대 7시간을 강의에 참여할 수 있다면 07:00로, 최대 12시간 12분를 강의에 참여할 수 있다면 12:12으로 출력한다.)

제한

  • 1 ≤ $N$ ≤ 5×102
  • 1 ≤ $M$ ≤ 105
  • 1 ≤ $S$의 길이 ≤ 20
  • $S$는 공백없는 알파벳 소문자로만 이루어져 있다.
  • 30분 ≤ 수업시간($Y$ - $X$) ≤ 180분
  • 1분 ≤ $Z$ ≤ 60분

예제 입력 1

4 5
hightech 10:00 10:50
leehogwan 11:00 11:50
ohogwan 11:50 13:00
jeongsuck 13:00 14:00
hightech leehogwan 00:03
hightech jeongsuck 00:12
hightech ohogwan 00:03
leehogwan jeongsuck 00:10
ohogwan jeongsuck 00:03

예제 출력 1

03:41