Problem: Ken and Keiko are young, poor and busy. Short explanation: they are students, and ridden with part-time jobs. To make things worse, Ken lives in Hakodate and Keiko in Tokyo. They want to meet, but since they have neither time nor money, they have to go back to their respective jobs immediately after, and must be careful about transportation costs. Help them find the most economical meeting point.

Ken starts from Hakodate, Keiko from Tokyo. They know schedules and fares for all trains, and can choose to meet anywhere including their hometowns, but they cannot leave before 8am and must be back by 6pm in their respective towns. Train changes take no time (one can leave the same minute he/she arrives), but they want to meet for at least 30 minutes in the same city.

There can be up to 100 cities and 2000 direct connections, so you should devise an algorithm clever enough for the task.



Input

The input is a sequence of data sets.

The first line of a data set contains a single integer, the number of connections in the timetable. It is not greater than 2000.

Connections are given one on a line, in the following format.


Start_city HH:MM Arrival_city HH:MM price


Start_city and Arrival_city are composed of up to 16 alphabetical characters, with only the first one in upper case. Departure and arrival times are given in hours and minutes (two digits each, separated by ":") from 00:00 to 23:59. Arrival time is strictly after departure time. The price for one connection is an integer between 1 and 10000, inclusive. Fields are separated by spaces.

The end of the input is marked by a line containing a zero.

Output

The output should contain one integer for each data set, the lowest cost possible. This is the total fare of all connections they use.

If there is no solution to a data set, you should output a zero.

The solution to each data set should be given in a separate line.

Example

Input

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


Output

11000
0
11090

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100
#define BASE 480
#define MAX 600

enum Type{
	A,
	B,
};

struct Edge{
	Edge(int arg_to,int arg_cost,int arg_start_time,int arg_arrive_time){
		to = arg_to;
		cost = arg_cost;
		start_time = arg_start_time;
		arrive_time = arg_arrive_time;
	}
	bool operator<(const struct Edge &arg) const{ //出発時刻の昇順
		return start_time < arg.start_time;
	}
	int to,cost,start_time,arrive_time;
};

struct Info{
	Info(int arg_node_id,int arg_sum_cost,int arg_current_time){
		node_id = arg_node_id;
		sum_cost = arg_sum_cost;
		current_time = arg_current_time;
	}
	bool operator<(const struct Info &arg) const{ //総コストの昇順(PQ)
		return sum_cost > arg.sum_cost;
	}
	int node_id,sum_cost,current_time;
};

struct Data{
	Data(int arg_rev_start_time,int arg_sum_cost){
		rev_start_time = arg_rev_start_time;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct Data &arg) const{ //帰宅開始時刻の昇順
		return rev_start_time < arg.rev_start_time;
	}
	int rev_start_time,sum_cost;
};

int N;
int node_index;
int min_cost[2][NUM][601],return_min_cost[NUM][601];
int A_id,B_id;
vector<int> work[2][NUM];
vector<Data> return_start[NUM];
const string start_A = "Hakodate";
const string start_B = "Tokyo";

map<string,int> MAP;
map<int,int> CALC;
vector<Edge> G[NUM];

//時刻を分に直す
int getNUM(char work[6]){

	int hour = 10*(work[0]-'0')+(work[1]-'0');
	int minute = 10*(work[3]-'0')+(work[4]-'0');

	return 60*hour+minute;
}

//8時～18時の時間帯か
bool rangeCheck(int tmp_time){
	if(tmp_time >= BASE && tmp_time <= BASE+MAX)return true;
	else{
		return false;
	}
}

void dijkstra(Type type,int start_id){

	for(int i = 0; i < node_index; i++){
		for(int k = 0; k <= MAX; k++){
			min_cost[type][i][k] = BIG_NUM;
		}
	}

	min_cost[type][start_id][0] = 0; //8時に出発

	priority_queue<Info> Q;
	Q.push(Info(start_id,0,BASE));

	int next_node,next_cost,next_time;

	while(!Q.empty()){

		if(Q.top().sum_cost > min_cost[type][Q.top().node_id][Q.top().current_time-BASE]){
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){
				//既に出発している、または有効時間外ならSKIP
				if(Q.top().current_time > G[Q.top().node_id][i].start_time)continue;
				if(rangeCheck(G[Q.top().node_id][i].start_time) == false || rangeCheck(G[Q.top().node_id][i].arrive_time) == false)continue;

				next_node = G[Q.top().node_id][i].to;
				next_cost = Q.top().sum_cost+G[Q.top().node_id][i].cost;
				next_time = G[Q.top().node_id][i].arrive_time;

				if(min_cost[type][next_node][next_time-BASE] > next_cost){

					min_cost[type][next_node][next_time-BASE] = next_cost;
					Q.push(Info(next_node,next_cost,next_time));
				}
			}
			Q.pop();
		}
	}
}

int rev_dijkstra(int start_id){

	int ret = BIG_NUM;
	int next_node,next_cost,next_time;
	int A_min,B_min;
	priority_queue<Info> Q;

	for(int p = 0; p < return_start[start_id].size(); p++){ //start時刻を全探索

		int start_time = return_start[start_id][p].rev_start_time;
		int start_cost = return_start[start_id][p].sum_cost;

		for(int a = 0; a < node_index; a++){
			for(int k = start_time-BASE; k <= MAX; k++)return_min_cost[a][k] = BIG_NUM;
		}

		return_min_cost[start_id][start_time-BASE] = 0; //★帰宅のコスト
		Q.push(Info(start_id,0,start_time));

		A_min = BIG_NUM;
		B_min = BIG_NUM;

		while(!Q.empty()){

			if(Q.top().sum_cost > return_min_cost[Q.top().node_id][Q.top().current_time-BASE]){
				Q.pop();
			}else{

				for(int i = 0; i < G[Q.top().node_id].size(); i++){
					//既に出発している、または有効時間外ならSKIP
					if(Q.top().current_time > G[Q.top().node_id][i].start_time)continue;
					if(rangeCheck(G[Q.top().node_id][i].start_time) == false || rangeCheck(G[Q.top().node_id][i].arrive_time) == false)continue;

					next_node = G[Q.top().node_id][i].to;
					next_cost = Q.top().sum_cost+G[Q.top().node_id][i].cost;
					next_time = G[Q.top().node_id][i].arrive_time;

					if(return_min_cost[next_node][next_time-BASE] > next_cost){
						return_min_cost[next_node][next_time-BASE] = next_cost;

						Q.push(Info(next_node,next_cost,next_time));
					}
				}
				Q.pop();
			}
		}

		for(int time = start_time-BASE; time <= MAX; time++){
			if(return_min_cost[A_id][time] != BIG_NUM){
				A_min = min(A_min,return_min_cost[A_id][time]);
			}
			if(return_min_cost[B_id][time] != BIG_NUM){
				B_min = min(B_min,return_min_cost[B_id][time]);
			}
		}

		if(A_min == BIG_NUM || B_min == BIG_NUM)continue;

		ret = min(ret,start_cost+A_min+B_min);
	}
	return ret;
}

void func(){

	MAP.clear();
	for(int i = 0; i < NUM; i++)G[i].clear();

	node_index = 0;

	string start,arrival;
	char start_buf[6],arrive_buf[6];
	int start_time,arrive_time;
	int price,start_id,arrive_id;

	for(int loop = 0; loop < N; loop++){
		cin >> start >> start_buf >> arrival >> arrive_buf >> price;

		auto at = MAP.find(start);

		if(at == MAP.end()){
			MAP[start] = node_index;
			start_id = node_index;
			node_index++;

		}else{
			start_id = MAP[start];
		}

		at = MAP.find(arrival);

		if(at == MAP.end()){
			MAP[arrival] = node_index;
			arrive_id = node_index;
			node_index++;

		}else{
			arrive_id = MAP[arrival];
		}

		start_time = getNUM(start_buf);
		arrive_time = getNUM(arrive_buf);

		if(rangeCheck(start_time) == false || rangeCheck(arrive_time) == false)continue;

		G[start_id].push_back(Edge(arrive_id,price,start_time,arrive_time));
	}

	A_id = MAP[start_A];
	B_id = MAP[start_B];

	//函館、東京から、各都市への到着可能時刻と、同時刻での最小コストを求める
	dijkstra(A,A_id);
	dijkstra(B,B_id);

	for(int town = 0; town < node_index; town++){

		work[A][town].clear();
		work[B][town].clear();

		return_start[town].clear();
	}

	int rev_start_time,tmp_cost;

	//各町から、函館or北海道への、帰宅開始可能時刻をworkにpushする
	for(int town = 0; town < node_index; town++){
		for(int time = 0; time <= MAX; time++){

			if(min_cost[A][town][time] != BIG_NUM){
				work[A][town].push_back(time+BASE);
			}

			if(min_cost[B][town][time] != BIG_NUM){
				work[B][town].push_back(time+BASE);
			}
		}

		//★最低30分会うので、帰宅開始可能時刻と、そのコストを求める★
		if(work[A][town].size() == 0 || work[B][town].size() == 0)continue;

		CALC.clear();

		for(int time = 1; time <= MAX; time++){
			min_cost[A][town][time] = min(min_cost[A][town][time],min_cost[A][town][time-1]);
			min_cost[B][town][time] = min(min_cost[B][town][time],min_cost[B][town][time-1]);
		}

		for(int i = 0; i < work[A][town].size(); i++){
			for(int k = 0; k < work[B][town].size(); k++){
				rev_start_time = max(work[A][town][i],work[B][town][k])+30;
				if(!rangeCheck(rev_start_time))continue;

				auto at2 = CALC.find(rev_start_time);
				tmp_cost = min_cost[A][town][work[A][town][i]-BASE]+min_cost[B][town][work[B][town][k]-BASE];

				if(at2 == CALC.end() || tmp_cost < CALC[rev_start_time]){
					CALC[rev_start_time] = tmp_cost;
				}
			}
		}

		for(auto at3: CALC){
			return_start[town].push_back(Data(at3.first,at3.second));
		}
		sort(return_start[town].begin(),return_start[town].end());
	}

	//各町から、出発時刻別の、函館または東京への帰宅最短コストを求める
	int ans = BIG_NUM;
	int ret;

	for(int start_town = 0; start_town < node_index; start_town++){
		if(return_start[start_town].size() == 0)continue; //そもそも会えない街ならSKIP

		ret = rev_dijkstra(start_town);
		if(ret == BIG_NUM)continue; //函館または東京に戻れないならSKIP

		ans = min(ans,ret);
	}

	if(ans == BIG_NUM){
		printf("0\n");
	}else{
		printf("%d\n",ans);
	}
}

int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}
	return 0;
}