UVA1079 A Careful Approach

## 问题描述 请你想象你是一个空中交通管制员。每一架飞机都有一个安全着陆时间窗。你的指令必须要符合每个飞机的时间窗。另外，飞机的着陆时间点要尽量均匀，使得连续两次着陆的最小间隔尽量大。例如，如果三架飞机分别着陆于10:00am、10:05am、10:15am，那么最小间隔是五分钟，在头两架飞机之间。所有间隔不一定一样，但是最小的间隔要尽量大。

输入多组数据。每个数据第一行为一个整数$n(2 ≤ n ≤ 8)$，为飞机架数。接下来$n$行，每行两个整数$a_i$，$b_i$表示这架飞机只能在闭区间$[a_i,b_i]$里降落。$a_i$和$b_i$的单位是分钟，并满足$0 ≤ a_i ≤ b_i ≤ 1440$。输入的最后一行是一个零。

对于每组数据，先输出第几组，然后输出最小间隔，单位为分和秒，舍入到最近的整数（四舍五入）。格式参见样例。 ## 输入输出样例 ### 样例输入 ``` 3 0 10 5 15 10 15 2 0 10 10 20 0 ``` ### 样例输出 ``` Case 1: 7:30 Case 2: 20:00 ```