You are addicted to watching TV, and you watch so many TV programs every day. You have been in trouble recently: the airtimes of your favorite TV programs overlap.

Fortunately, you have both a TV and a video recorder at your home. You can therefore watch a program on air while another program (on a different channel) is recorded to a video at the same time. However, it is not easy to decide which programs should be watched on air or recorded to a video. As you are a talented computer programmer, you have decided to write a program to find the way of watching TV programs which gives you the greatest possible satisfaction.

Your program (for a computer) will be given TV listing of a day along with your score for each TV program. Each score represents how much you will be satisfied if you watch the corresponding TV program on air or with a video. Your program should compute the maximum possible sum of the scores of the TV programs that you can watch.



Input

The input consists of several scenarios.

The first line of each scenario contains an integer N (1 ≤ N ≤ 1000) that represents the number of programs. Each of the following N lines contains program information in the format below:

T Tb Te R1 R2

T is the title of the program and is composed by up to 32 alphabetical letters. Tb and Te specify the start time and the end time of broadcasting, respectively. R1 and R2 indicate the score when you watch the program on air and when you have the program recorded, respectively.

All times given in the input have the form of “hh:mm” and range from 00:00 to 23:59. You may assume that no program is broadcast across the twelve midnight.

The end of the input is indicated by a line containing only a single zero. This is not part of scenarios.

Output

For each scenario, output the maximum possible score in a line.

Example

Input

4
OmoikkiriTV 12:00 13:00 5 1
WaratteIitomo 12:00 13:00 10 2
WatarusekennhaOnibakari 20:00 21:00 10 3
SuzumiyaharuhiNoYuuutsu 23:00 23:30 100 40
5
a 0:00 1:00 100 100
b 0:00 1:00 101 101
c 0:00 1:00 102 102
d 0:00 1:00 103 103
e 0:00 1:00 104 104
0


Output

121
207
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;
static const double EPS = 1e-9;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SS stringstream
#define DBG1(a) rep(_X,sz(a)){printf("%d ",a[_X]);}puts("");
#define DBG2(a) rep(_X,sz(a)){rep(_Y,sz(a[_X]))printf("%d ",a[_X][_Y]);puts("");}
#define bitcount(b) __builtin_popcount(b)
#define REP(i, s, e) for ( int i = s; i <= e; i++ )  
#define fi first
#define se second
int dp[1024][1024];
struct Item{
	int l,r,S1,S2;
};
vector<Item> item;
bool operator < (const Item &a,const Item &b){
	if( a.l != b.l ) return a.l < b.l;
	return a.r < b.r;
}

int nextNode[1024];
int n;
int dfs(int x,int y){
	if( dp[x][y] != -1) return dp[x][y];
	int ans = 0;
	int xNext = nextNode[x];
	int yNext = nextNode[y];
	if( x == n && y == n ) return 0;
	else if( x == n ){
		return dp[x][y] = max( dfs(x,y+1) , dfs(x,yNext)+item[y].S2 );
	}else if( y == n){
		return dp[x][y] = max( dfs(x+1,y) , dfs(xNext,y)+item[x].S1 );
	}
	if( y < x ){
		ans = max( ans , dfs(x,y+1) );
		ans = max( ans , dfs(x,yNext) + item[y].S2 );
	}else if( x == y ){
		ans = max( ans , dfs(x+1,y+1) );
		ans = max( ans , dfs(xNext,y+1) + item[x].S1);
		ans = max( ans , dfs(x+1,yNext) + item[y].S2);
	}else{
		ans = max( ans , dfs(x+1,y) );
		ans = max( ans , dfs(xNext,y) + item[x].S1 );
	}
	return dp[x][y] = ans;
}


int conv(string t){
	t[2] = ' ';
	stringstream ss(t);
	int h,m;
	ss >> h >> m;
	
	return h * 60 + m;
}

int main(){
	while(cin >> n && n){
		memset(dp,-1,sizeof(dp));
		item.clear();
		for(int i = 0 ; i < n ; i++){
			string nm;
			string a,b;
			cin >> nm >> a >> b;
			int r1,r2;
			cin >> r1 >> r2;
			item.push_back({conv(a),conv(b),r1,r2});
			//cout << a << " " << b << endl;
		}
		sort(item.begin(),item.end());
		for(int i = 0 ; i < n ; i++){
			nextNode[i] = n;
			for(int j = i+1 ; j < n ; j++)
				if( item[i].r <= item[j].l ){
					nextNode[i] = j;
					break;
				}
		}
		cout << dfs(0,0) << endl;
	}
	
	
}