e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Cleaning up the Snow

Cleaning up the Snow

In winter, when days become shorter, and nights longer, it is necessary to think about cleaning up the streets from the snow. But the budget of our city is very small that is why we have just only one snowmobile. The roads must be cleaned out without regard to it. Consequently each time when falls a lot of snow, at night the snowmobile of our city drives out from a garage and goes around all the city cleaning the roads. Find the minimum time a snowmobile need o clean all the roads and return back to a garage? It is known that:

  • A snowmobile can clean out only one road for a one passage-way.
  • All roads are lines with one bar of motion in every direction.
  • A snowmobile can return on any crossing in any direction, and also can turn out in a deadlock.
  • During the cleaning up the snow a snowmobile moves with speed 20 Km/hour, and with speed 50 Km/Hour on the already cleaned road.
  • Opportunity to drive all the roads always exists.

Input

The coordinates x, y (-30000x, y30000) of the hangar (in meters), where from the snowmobile starts to move, are given in the first line. Then the coordinates (in meters) of the beginning and the end of the streets (4 integers in each line) are given. There can be up to 100 streets.

Output

Time in hours and minutes needed for clearing all the roads and returning to the hangar. Time must be rounded to the minutes.

Time limit 1 second
Memory limit 64 MiB
Input example #1
0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000
Output example #1
3:55