Problem F: TV Watching

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 T_b T_e R₁ R₂

T is the title of the program and is composed by up to 32 alphabetical letters. T_b and T_e specify the start time and the end time of broadcasting, respectively. R₁ and R₂ 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.

Sample 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 for the Sample Input

121
207

---