Problem B
Class Scheduling

Drill field at Virginia Tech during class change

John Hokie is a student at Virginia Tech and is working on completing his course request for next semester. This semester he was cursed by having an 8am lecture and a $3$ hour 7pm lab. The days of getting on campus before the sun rises and leaving after it sets are surely over next semester! Mr. Hokie knows exactly what classes he needs to take and scoured the timetable to compile all of the section times for each class he needs to take on a particular day.

He desires a schedule that needs him to be on campus for the shortest amount of time. That is, he wants the schedule with the shortest time between the start of his first class and the end of his last class. He’s curious what the minimum amount of time he will need to be on campus for is and needs your help to quickly find it out. Keep in mind, though, that he will need at least $15$ minutes between classes to have enough time to walk across campus. John is serious about being on time to his classes!

Input

The first line contains an integer $n$ ($1 \le n \le 8$) denoting the number of classes he needs to take. This is followed by $n$ sections, where the first line contains $s, k$, where $s$ is the name of the class and is composed of up to $8$ lowercase letters and numbers, and $k$ is an integer ($1 \le k \le 10$) denoting the number of sections for that class. The next $k$ lines in this section contain two times $t_1, t_2$, denoting the start and end time of the class section where ($8:00 \le t_1 < t_2 \le 20:00$). Each time is denoted in 24-hour format following the format $h:m$ where leading zeroes in $h$ and $m$ may be excluded. It can also be guaranteed that the duration of all classes is between $45$ minutes and $90$ minutes and that no two sections for a given class will overlap. Note that due to professors’ teaching styles and scheduling constraints, different sections of the same class may be of different durations. Additionally, you can assume there is always at least $1$ valid schedule.

Output

Output a single number, which is the minimum number of minutes that John Hokie must stay on campus with the shortest possible schedule that covers all his classes by selecting exactly one section of each class.

3
cs101 3
13:0 14:15
8:0 8:50
10:0 11:15
cs103 1
9:30 10:30
math334 3
15:0 16:0
12:0 13:0
10:0 11:15

300