페리 이동

노르웨이의 여러 이동 경로에는 육지와 피오르드가 번갈아 나타난다. 출발지에서 목적지까지 가려면 육지 구간에서는 자동차를 운전하고, 피오르드 구간에서는 정해진 시간표에 따라 운항하는 페리를 타야 한다.

가장 빠르게 이동하는 방법은 모든 도로 구간을 최고 속도인 80 km/h로 달리고, 각 피오르드에 도착하면 탈 수 있는 가장 이른 페리를 기다려 타는 것이다. 하지만 그렇게 빠르게 운전하는 것은 비용이 많이 들고 환경에도 좋지 않다. 따라서 먼저 가능한 최소 총 이동 시간을 구하고, 그 최소 시간을 그대로 달성할 수 있는 가장 낮은 일정한 운전 속도를 구해야 한다.

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트의 첫 줄에는 이동해야 하는 구간의 수 s (s > 0)가 주어진다. 이어지는 s개의 줄에는 실제 이동 순서대로 각 구간의 정보가 주어진다. 각 줄은 시작 지점 이름, 끝 지점 이름, 구간 종류로 시작한다.

육지 구간은 start end road length 형식이다. length는 km 단위의 양의 정수 거리이다.

피오르드 구간은 start end ferry crossing f minute1 ... minutef 형식이다. crossing은 페리를 타고 건너는 데 걸리는 시간(분)이고, f (f > 0)는 매시간 운항하는 페리의 수이다. 뒤따르는 f개의 정수는 그 한 시간 안에서 페리가 출발하는 분을 나타내며, 증가하는 순서로 주어진다. 같은 시간표가 매시간 반복된다.

각 데이터 세트는 총 이동 시간이 10시간을 넘지 않도록 주어진다. 이동은 항상 어떤 시각의 정각, 즉 x:00에 시작한다고 가정한다. 첫 줄에 0이 주어지면 입력이 끝난다.

각 데이터 세트마다 한 줄에 데이터 세트 번호, 최소 총 이동 시간, 그리고 그 최소 이동 시간을 달성할 수 있는 최소 운전 속도를 출력한다. 출력 형식은 Test Case k: HH:MM:SS v이다. 속도는 소수점 아래 셋째 자리에서 반올림하여 소수점 둘째 자리까지 출력한다.