Snow Clearing

Time limit1sMemory limit128 MB

Summary

Find the minimum time to plow every directed lane of a city's two-way streets and return to the hangar, given faster travel on already-cleared lanes.

Level: Hard8 of 10
Topics: Graph, Shortest path, Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

As the days grow shorter and the nights grow longer, the city turns its thoughts to snow clearing. Because of budget cuts, the city has exactly one snow plow. The plow can clear exactly one lane of a road in a single pass. Whenever snow has fallen, the plow leaves its hangar and tours the city, plowing as it goes. What is the minimum time the plow needs to clear every lane of every road?

Input

The first line contains two integers: the x and y coordinates of the hangar (in metres). Up to 100 lines follow. Each gives the coordinates (in metres) of the beginning and end of a street. All roads are perfectly straight, with one lane in each direction. The plow may turn in any direction (including a U-turn) at any intersection, and may turn around at the end of any street. The plow travels at 20 km/h while it is plowing and at 50 km/h on a lane that has already been plowed. Every street is reachable from the hangar.

Output

Print the time needed to plow every lane and return to the hangar, given as hours and minutes separated by a colon (for example, 3:55), with the minutes written as exactly two digits. Round the time to the nearest minute.

Examples8

Example 1

Input

0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000

Expected output

3:55

Example 2
Input
```
0 0
0 0 1000 0
```
Expected output
```
0:06
```
Example 3
Input
```
0 0
0 0 10000 0
```
Expected output
```
1:00
```
Example 4
Input
```
99999 99999
0 0 10000 0
```
Expected output
```
1:00
```

Example 5

Input

-5000 -5000
-2000 -8000 -2000 8000

Expected output

1:36

Example 6

Input

0 0
0 0 3000 4000
3000 4000 3000 9000

Expected output

1:00

Example 7

Input

10 20
0 0 7000 0
7000 0 7000 3000
7000 3000 0 3000
0 3000 0 0

Expected output

2:00

Example 8
Input
```
0 0
0 0 20000 10000
```
Expected output
```
2:14
```