The postal department wants to extend its services to naval vehicles. However, delivering presents to moving targets can be a real hassle. The problem is that you have to fly your mail helicopter to where the vessel will be, instead of where it is now. The Postmaster General has asked you to write a program that helps him do that, and, given a set of vessels, plan a route that will take the minimum amount of time to complete.
You will be given the initial coordinates of the helicopter and each vessel at sea. Each vessel is travelling constantly at a heading and speed specified by the velocity vector (vx, vy), meaning that after 1 hour it would have travelled vx km in the x direction and vy km in the y direction (vx and vy may be negative). The length of the vector is the speed. The helicopter is capable of travelling at a constant speed in any direction (assume that acceleration and deceleration are instantaneous). It must land on each vessel at least once, and it takes 5 minutes at each stop to unload the presents. The helicopter can carry all the mail for all the vessels without having to return to the post office. All coordinates have km as units, and all velocities and speeds have km/h as units.
Find the shortest time for the helicopter to deliver mail to each vessel and return to its starting location.
The input consists of a number of cases. Each case starts with a line containing the integer N (1 <= N <= 8) specifying the number of vessels. The next N lines contain 4 integers separated by a space: the initial (x,y) coordinates of the i-th vessel and its velocity vector. The last line of each case contains 3 integers specifying the initial (x,y) coordinates of the helicopter and its speed. The end of input is indicated by a case that starts with N = 0, and this last case should not be processed. All input integers have absolute value at most 1000. You may assume that the helicopter travels at a greater speed than every vessel. Note that the paths of the vessels may cross each other or even the helicopter's initial location, but the captains will just make minor course corrections to avoid collisions, so you don't have to take this into account.
For each case, print its case number, a colon, followed by the minimum amount of time needed to complete the delivery in the format:
Case a: b hour(s) c minute(s) d second(s)
where a, b, c, d are appropriate non-negative integers, and c and d are at most 59. The time should be rounded up to the next second.
| Sample Input | Sample Output |
|---|---|
5 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 0 0 1 3 1 2 3 4 2 2 40 23 7 8 22 10 0 0 50 0 |
Case 1: 15 hour(s) 0 minute(s) 0 second(s) Case 2: 5 hour(s) 59 minute(s) 50 second(s) |