Catch the Plane#11554
Your plane to the ICPC World Finals departs soon, and the only way to reach the airport is by bus. Unfortunately, some drivers are considering going on strike, so you are not sure whether you will arrive on time. Your goal is to plan the trip in such a way as to maximize the probability of catching your flight.
You are given a detailed map of the city showing all bus stations. You are currently at station , and the airport is located at station . You have the complete schedule: for each bus you know the departure time from its starting station and the arrival time at its destination. Moreover, for every bus you are given the probability that it will actually operate and that its driver will not go on strike. Assume that all these events are independent. In other words, the probability that a particular bus runs according to the schedule does not depend on whether any other bus is running.
If you arrive at a station strictly before a bus departs, you may try to board it. However, if you arrive exactly at the departure time, you will not have enough time to get on the bus. It is impossible to know in advance whether a bus will operate as scheduled — you will only find out at the moment you attempt to board it. If several buses depart from the station at the same time, you may try to board only one of them.
Consider the schedule shown in the figure. It lists the departure and arrival stations for several routes, as well as their departure and arrival times. Next to some of the routes, the probability that the bus will actually operate is given. For routes where the probability is not specified, it is assumed to be .
You may try to take the earliest bus. If it runs, it will bring you directly to the airport, and there is nothing to worry about. Otherwise, the situation becomes more complicated. You can take the second bus to station . It will certainly depart, but then you will miss the third bus in the list, which would have brought you to the airport in time. The fourth bus you can still catch has a probability of only of operating. This is too risky, so it is better to stay at station and wait for the fifth bus. If you manage to board it, you can then try to transfer to the sixth bus to the airport; if it does not run, you will still have a chance to return to station and catch the last bus going directly to the airport.
The first line contains two integers m~(1 \le m \le 10^6) and n~(2 \le n \le 10^6) — the number of bus routes and the number of stations in the city. The next line contains one integer k~(1 \le k \le 10^{18}) — the time by which you must arrive at the airport.
Each of the following lines describes one route. Each line contains integers and b~(0 \le a, b < n, a \ne b) — the starting and ending stations. Then follow integers and t~(0 \le s < t \le k) — the departure time from station and the arrival time at station . The last value in the line is a number p~(0 \le p \le 1, with at most digits after the decimal point), denoting the probability that the bus will operate according to the schedule.
Print the probability that you will catch your plane if you act optimally. Your answer must have an absolute or relative error of at most 10^{-6}.
Example 1
Example 2