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.
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 ghh:mmh 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.
For each scenario, output the maximum possible score in a line.
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