Hide

Problem B
Breaking (Is) Bad

Brittany is trying to set up her class schedule for the Fall 2019 semester. Since she is a commuter student, she wants to schedule her classes close to one another so that she can arrive on campus, attend class, and go back home without long breaks between classes.

Given several potential class schedules for one day, Brittany needs to determine the minimum possible total time spent between classes throughout that entire day.

Input

The input begins with a single line containing an integer $n$ ($2 \le n \le 10$). The next $n$ lines each contain a potential schedule for the day. Each schedule consists of at least $1$ and at most $8$ class times, separated by spaces.

Each class time is formatted as hourStart:minuteStart-hourEnd:minuteEnd, where the hours range from $0$$23$ and the minutes range from $0$$59$. A leading zero is included for single-digit minutes, but there is no leading zero for single-digit hours. Every class lasts at least $1$ minute, and the number of minutes between each ending time and the next starting time is always non-negative. Note that the time between consecutive classes can be zero—Brittany is an accomplished sprinter, so this doesn’t bother her.

Output

Output a single line containing the minimum possible total minutes Brittany can have between classes throughout the day. If any of the potential schedules have only one class, output 0.

Sample Input 1 Sample Output 1
2
9:00-9:55 10:05-11:30 11:35-12:30
9:10-10:05 10:45-11:45
15
Sample Input 2 Sample Output 2
2
9:40-11:05
9:40-11:05 11:20-12:45
0
CPU Time limit 1 second
Memory limit 1024 MB
Author
Kriangsiri Malasri
Source Consortium for Computing Sciences in Colleges Mid-South Programming Contest 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in