Catch the Plane

Your plane to the ICPC Finals leaves soon, and the only way to reach the airport is by bus. Some of the bus drivers are considering a strike, so you do not know whether you can reach the airport on time. Plan your journey so that the probability of catching the plane is as large as possible.

You have a detailed map of the city with every bus station on it. You are at station 0 and the airport is at station 1. You also have a complete schedule of when each bus leaves its start station and when it arrives at its destination station. For every bus you know the probability that it runs as scheduled, as opposed to its driver going on strike and taking the bus out of service. All these events are independent: learning whether some buses run does not change the probability that another bus runs.

If you reach a station before a bus departs, you can transfer to that bus. If you reach the station exactly at the departure time, you do not have enough time to board. You cannot check in advance whether a bus runs as planned. You find out only when you try to board it, so if two or more buses leave a station at the same time, you can try only one of them.

Figure 1: the bus schedule of the first example.

Look at the schedule in Figure 1. It lists the start and destination stations of several bus routes with their departure and arrival times, and next to some routes the probability that the route runs. A route with no probability written next to it always runs. You can try the first route. If that bus runs, it takes you straight to the airport and you can stop worrying. If it does not, things get harder. You could take the second route to station 2. That bus is certain to leave, but then you are too late for the third route, which would have delivered you to the airport on time. The fourth route, which you can still catch, runs with probability only 0.1. That is a bad bet, so staying at station 0 and waiting for the fifth route is better. If you catch the fifth route, you can try the sixth route to the airport, and if that one does not run, you still have the chance to return to station 0 and take the last route straight 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 buses and the number of stations in the city. The second line contains one integer $k$ ($1 \le k \le 10^{18}$), the time by which you must be at the airport.

Each of the next $m$ lines describes one bus. The line contains the start station $a$ and the destination station $b$ ($0 \le a, b < n$, $a \ne b$), then the departure time $s$ from station $a$ and the arrival time $t$ at station $b$ ($0 \le s < t \le k$), then the probability $p$ ($0 \le p \le 1$, with at most 10 digits after the decimal point) that the bus runs as planned.

Print the probability that you catch your plane when you act optimally. Print it on one line, rounded to six digits after the decimal point and always written with six digits. A probability of exactly $0.7$ is printed as 0.700000. No input has an answer that sits on the rounding boundary of the sixth digit.