차량 호출

Jamal은 새로 차량 호출 사업을 시작했다. 이 사업은 다음과 같이 운영된다. 고객이 원하는 출발 시각보다 적어도 $12$시간 전에 출발지에서 도착지로 가는, 지정된 출발 시각에 시작하는 이동을 주문한다. Jamal은 과거에 합승을 고려한 적이 있지만, 진행 중인 팬데믹 때문에 현재는 주문된 각 이동이 다음 이동이 시작되기 전에 끝난다. Jamal의 회사에는 현재 서비스 지역의 배치와 각 도로를 주행하는 데 필요한 시간의 상한이 있다. 언젠가는 교통 데이터를 반영해 지도를 동적으로 만들고 싶지만, 지금은 고정 비용만 가지고 작업해야 한다.

각 이동이 미리 예약되기 때문에 Jamal의 회사는 경로 계획을 최적화하고 기사에게 매력적인 사업 모델을 제공할 수 있다. 회사는 다음과 같이 운영한다. $8$시간마다 Jamal은 기사 집합을 선택해 한 교대 근무 동안 고객을 태우고 내려주도록 하며, 이는 고객이 원하는 일정에 맞춘다. 기사는 완료한 이동 수가 아니라 근무한 교대 수에 따라 급여를 받는다. Jamal은 이 모델이 현재 차량 호출 사업보다 기사에게 더 만족스럽다는 것을 알았다. 현재 사업에서 기사는 얼마나 많은 호출을 받을 수 있을지, 따라서 얼마를 벌지 알 수 없다. 반면 Jamal의 사업은 기사가 근무한 모든 교대에 대해 급여를 지급하므로, 기사는 승객이 호출하기를 차 안에서 기다리는 대신 교대를 근무하면 돈을 벌고, 근무가 필요 없으면 다른 일로 시간을 보낼 수 있다.

안타깝게도 Jamal은 사업가에 가까워 회사 코드 작성에 도움이 필요하다. 특히 8시간 창 안에서 주문된 이동 집합이 주어졌을 때 해당 교대에 고용해야 하는 최소 기사 수를 구하는 알고리즘이 없다. 이 중요한 작업을 도와줄 수 있는가?

그림 1: 예제 입력의 그림. 예약된 이동은 각각의 출발 시각과 함께 빨간 점선으로 표시된다. 최적해는 한 기사가 시각 $0$에 $2$에서 $3$으로 가는 이동을 완료한 뒤, 시각 $8$에 도착하도록 위치 $1$로 이동하고, 이어서 $1$에서 $2$로 가는 이동을 완료하는 것이다. 두 번째 기사는 $3$에서 $4$로 가는 이동을 완료할 수 있다.

입력은 한 줄에 세 정수로 시작한다. $n$ ($2 \leq n \leq 100$)은 서비스 지역 모델에서 승차 또는 도착 위치의 수, $m$ ($1 \leq m \leq n\*(n-1)$)은 서비스 지역의 일방통행 도로 수, $k$ ($1 \leq k \leq 1000$)는 반드시 수행해야 하는 요청된 이동 수이다. 다음 $m$개 줄에는 각각 세 정수 $u$, $v$, $w$ ($1 \leq u,v \leq n$, $u \neq v$, $1 \leq w < 480$)가 주어지며, 위치 $u$에서 위치 $v$로 가는 데 $w$분이 걸리는 도로가 있음을 나타낸다. 두 위치 $u$와 $v$ 사이에는 $u$에서 $v$로 가는 도로와 $v$에서 $u$로 가는 도로가 모두 있을 수 있지만, 어느 두 위치 사이에도 한 방향으로는 도로가 최대 하나이다. 다음 $k$개 줄에는 각각 세 정수 $u$, $v$, $t$ ($1 \leq u,v \leq n$, $u \neq v$, $0 \leq t < 480$)가 주어지며, 위치 $u$에서 분 $t$에 출발해 위치 $v$로 가는 이동이 요청되었음을 나타낸다. 같은 출발 위치에서 같은 시각에 요청된 이동이 여러 개 있을 수 있고, 같은 도착 위치에 같은 시각에 도착하는 이동이 여러 개 있을 수 있다. 모든 위치는 다른 모든 위치에서 도달할 수 있음이 보장된다.

모든 이동을 완료하기 위해 이 교대에 고용해야 하는 최소 기사 수를 나타내는 정수 하나를 출력한다. 도로는 필요한 만큼 많은 기사가 사용할 수 있다. 승차와 하차에 걸리는 시간은 $0$분이라고 가정한다. 같은 위치에서 승차하거나 하차하는 것은 이동을 지연시키지 않는다. 고용된 기사는 어떤 출발 위치로든 운전해 갈 수 있어 분 $0$에 어떤 이동이든 태울 준비가 되어 있고, 분 $480$ 이후에 끝나는, 분 $480$ 전에 요청된 이동도 완료할 의향이 있다고 가정한다. 고객은 원하는 승차 시각에 정확히 태워야 한다.