Traffic Lights - 2#207
Oleksiy works as a courier for a package delivery service. Today he has an important order — to deliver an urgent package to a client who lives on the other side of the city. The problem is that the city has a complex road system, and there is a traffic light in the middle of each road.
To optimize the couriers' work, the delivery service management installed a special traffic light system. Each traffic light has only two colors: red and green (without yellow), and each traffic light has its own switching period. All traffic lights are synchronized and switch simultaneously at the beginning of the working day.
Oleksiy knows that when he reaches the middle of a road where a traffic light is installed, he must wait if the red light is on. The traffic light switches between green and red with a certain period: first, green lights up for half the period, then red lights up for the other half of the period, and so on.
Oleksiy wants to find the fastest route to the client. He starts his journey from intersection number , and the client's address is located near intersection number . Help him determine the minimum delivery time.
The first line contains the integers , , and the real number , where is the number of intersections, is the number of roads, and is Oleksiy's speed (N \leq 100, M < 10000, 0 < V \leq 100). Each of the following lines describes a road with four numbers — , , , , where is the starting intersection, is the ending intersection (A, B \leq N), is the length of the road, and is the switching period of the traffic light in the middle of the road (L, P \leq 100). Note that the numbers and can be fractional. Only one road can connect any two intersections.
Output a single real number with two decimal places — the minimum time in seconds for Oleksiy to reach the client.
Example 1