|
Problem E: Tape Recording |
Note: We see that recording TV shows is seen as copyright infringement in many countries. We feel sorry for that, and we believe that VHS tapes will always be part of our invaluable collective memory.
Jay is a huge TV lover. He spends all his leisure time in the world of TV programmes; soap operas, game shows, charity shows, news, cartoons, cookery programmes... Jay watches them all.
For many years there were only two TV channels in his town. In order not to miss any shows, Jay has bought two VHS tape recorders, so that he can record all shows on tapes and watch them at any time he wants. But now, more and more channels are in service, and Jay cannot afford buying more tape recorders. Thus, he would like to make the best use of the existing two recorders. Sometimes he would have to give up some great shows reluctantly. Moreover, he thinks that watching just part of a TV programme is no fun, so if he records a programme, he records the full show.
To all shows in the TV schedule Jay has assigned a fun value in the range [1, 5]. Your job is to write a program to compute the maximum total fun that Jay can get if he uses his recorders optimally.
Input consists of several test cases. Each test begins with a line containing an integer n (1 ≤ n ≤ 100). Then n lines follow, each giving the starting time, ending time, fun value and name of a show. The times will be in the format HH:MM, ranging from 00:00 to 23:59. No shows share the same name within a list, and no names have more than 60 characters.
A day of TV broadcasting starts at 6 am. All TV programmes listed in the input are on the same day, and none will encompass 6 am. Also, the duration of any single show will not exceed the length of a tape, and the time taken to press the "Record" button etc. is negligible. You can further assume that Jay has a virtually unlimited supply of VHS tapes at home (just like any other TV maniac).
Input ends with a dummy case where n = 0. Your program should ignore this test case.
For each test case, output the maximum fun that Jay can get. Of course Jay will not record a same show in two tapes.
4 21:15-23:30 5 Shrek 21:30-23:55 5 Howl's Moving Castle 21:45-22:45 4 The Life of Mammals 22:45-23:15 2 Late News 0
Case 1: 11