Subway

Time limit1sMemory limit128 MB

Summary
Find the shortest travel time from home to school using walking and subway lines, rounding the answer to the nearest minute.
Level

Medium4 of 10

Topics
Shortest path, Graph, Geometry, Implementation
Solved
No attempts yet

Problem

You have just moved from a quiet neighbourhood to a big, noisy city. Instead of biking to school, you now have to walk and ride the subway, and you want to know how long the trip will take.

You walk at a speed of 10 km/h and the subway travels at 40 km/h. Assume you are lucky: whenever you reach a subway stop, a train is already there and you can board immediately. You may board and leave the subway any number of times and switch between different subway lines freely. Every subway line runs in both directions.

You may walk in a straight line between any two points, but you can only board or leave the subway at a stop.

Input

The input is a stream of integers separated by whitespace; the numbers may be split across several lines.

The first two integers are the xx and yy coordinates of your home, and the next two are the xx and yy coordinates of your school.

After that come one or more subway lines. Each subway line is given as the x,yx, y coordinates of its stops, in order along the line, and is terminated by the sentinel pair -1 -1. Every coordinate is a non-negative integer number of metres, adjacent stops are joined by a straight subway segment, and each line has at least two stops. There are at most 200200 subway stops in the whole city.

Output

Print a single integer: the time in minutes for the fastest possible trip from home to school, rounded to the nearest minute.

Examples1

  1. Example 1

    Input
    0 0 10000 1000
    0 200 5000 200 7000 200 -1 -1 
    2000 600 5000 600 10000 600 -1 -1
    
    Expected output
    21