描述：

健（Ken）和惠子（Keiko）年轻、贫穷且忙碌。简而言之：他们是学生，同时兼职多份工作。更糟糕的是，健住在函馆，惠子住在东京。他们想见面，但由于既没有时间也没有钱，他们必须在见面后立即返回各自的工作岗位，并且需要谨慎考虑交通费用。请帮助他们找到最经济的会面地点。

健从函馆出发，惠子从东京出发。他们知道所有列车的时刻表和票价，可以选择在任何城市（包括家乡）会面，但两人均不能在早上$8$点前出发，且必须在下午$6$点前返回各自的城市。$换乘时间忽略不计$（即到达后可以立即换乘），但会面时间必须至少为$30$分钟。

城市数量不超过$100$个，直达线路不超过$2000$条，因此需要设计一个高效的算法来解决该问题。

输入格式

输入由多个数据集组成。 每个数据集的第一行是一个整数，表示时刻表中的直达线路数量（不超过$2000$条）。

接下来的每行描述一条直达线路，格式如下：

出发城市 HH:MM 到达城市 HH:MM 票价
出发城市和到达城市由不超过$16$个字母组成，仅首字母大写。

出发和到达时间格式为HH:MM（$00:00$至$23:59$），且到达时间严格晚于出发时间。

票价为$1$至$10000$之间的整数。

字段之间用空格分隔。

输入以一行单独的$0$结束。

输出格式

对于每个数据集，输出一个整数，表示最低总票价（即两人使用的所有线路票价之和）。

如果无解，则输出$0$。

每个数据集的输出占一行。

示例输入

5  
Hakodate 08:15 Morioka 12:30 2500  
Morioka 14:05 Hakodate 17:30 2500  
Morioka 15:30 Hakodate 18:00 3000  
Morioka 14:30 Tokyo 17:50 3000  
Tokyo 08:30 Morioka 13:35 3000  
4  
Hakodate 08:15 Morioka 12:30 2500  
Morioka 14:04 Hakodate 17:30 2500  
Morioka 14:30 Tokyo 17:50 3000  
Tokyo 08:30 Morioka 13:35 3000  
18  
Hakodate 09:55 Akita 10:53 3840  
Hakodate 14:14 Akita 16:09 1920  
Hakodate 18:36 Akita 19:33 3840  
Hakodate 08:00 Morioka 08:53 3550  
Hakodate 22:40 Morioka 23:34 3550  
Akita 14:23 Tokyo 14:53 2010  
Akita 20:36 Tokyo 21:06 2010  
Akita 08:20 Hakodate 09:18 3840  
Akita 13:56 Hakodate 14:54 3840  
Akita 21:37 Hakodate 22:35 3840  
Morioka 09:51 Tokyo 10:31 2660  
Morioka 14:49 Tokyo 15:29 2660  
Morioka 19:42 Tokyo 20:22 2660  
Morioka 15:11 Hakodate 16:04 3550  
Morioka 23:03 Hakodate 23:56 3550  
Tokyo 09:44 Morioka 11:04 1330  
Tokyo 21:54 Morioka 22:34 2660  
Tokyo 11:34 Akita 12:04 2010  
0

示例输出

11000  
0  
11090

来源

Japan 2001