暂无测试数据。

Warning

数据有所加强

Background

ACM-ICPC World Final 2018

Description

Your plane to the ICPC Finals departs in a short time, and the only way to get to the airport is by bus.
Unfortunately, some of the bus drivers are considering going on strike, so you do not know whether
you can get to the airport on time. Your goal is to plan your journey in such a way as to maximize the
probability of catching your plane.

You have a detailed map of the city, which includes all the bus stations. 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
arrives at its destination station. Additionally, for each bus you know the probability that it is actually going to run as scheduled, as opposed to its driver going on strike and taking the bus out of service.

Assume all these events are independent. That is, the probability of a given bus running as planned does
not change if you know whether any of the other buses run as planned.

If you arrive before the departure time of a bus, you can transfer to that bus. But if you arrive exactly
at the departure time, you will not have enough time to get on the bus. You cannot verify ahead of time
whether a given bus will run as planned – you will find out only when you try to get on the bus. So if
two or more buses leave a station at the same time, you can try to get on only one of them.

表格待补充，其描述了Sample Input 1. 暂时不影响做题

Consider the bus schedule shown in Figure A.1. It lists the start and destination stations of several bus
routes along with the departure and arrival times. You have written next to some of these the probability
that that route will run. Bus routes with no probability written next to them have a 100% chance of
running. You can try catching the first listed bus. If it runs, it will take you straight to the airport, and you can stop worrying. If it does not, things get more tricky. You could get on the second listed bus to station 2. It is certain to leave, but you would be too late to catch the third listed bus which otherwise would have delivered you to the airport on time. The fourth listed bus – which you can catch – has only a 0.1 probability of actually running. That is a bad bet, so it is better to stay at station 0 and wait for the fifth listed bus. If you catch it, you can try to get onto the sixth listed bus to the airport; if that does not run, you still have the chance of returning to station 0 and catching the last listed bus straight to the airport.

Format

Input

The first line of input contains two integers \(m(1 \leqslant m \leqslant 10^6)\) and \(n(2 \leqslant n \leqslant 10^6)\), denoting the number of buses and the number of stations in the city. The next line contains one integer \(k (1 \leqslant k \leqslant 10^{18})\),denoting the time by which you must arrive at the airport.

Each of the next \(m\) lines describes one bus. Each line contains integers \(a\) and \(b\) \((0 \leqslant a, b \leqslant, a \ne b)\), denoting the start and destination stations for the bus. Next are integers \(s\) and \(t\) \((0 \leqslant s < t \leqslant k)\),giving the departure time from station \(a\) and the arrival time at station \(b\). The last value on the line is \(p\)(\(0 \leqslant p \leqslant 1\), with at most 10 digits after the decimal point), which denotes the probability that the bus will run as planned.

Output

Display the probability that you will catch your plane, assuming you follow an optimal course of action.
Your answer must be correct to within an absolute error of \(10^{-6}\).

Sample 1

Input

8 4
1000
0 1 0 900 0.2
0 2 100 500 1.0
2 1 500 700 1.0
2 1 501 701 0.1
0 3 200 400 0.5
3 1 500 800 0.1
3 0 550 650 0.9
0 1 700 900 0.1

Output

0.3124

Sample 2

Input

4 2
2
0 1 0 1 0.5
0 1 0 1 0.5
0 1 1 2 0.4
0 1 1 2 0.2

Output

0.7

Limitation

官方数据（50%）

对于所有的测试点，每个测试点分配10.0s的时限和512.0 MB的内存

加强数据（50%）

数据范围修改：\(1 \leqslant m \leqslant 2 \times 10^6, 2 \leqslant n \leqslant 2 \times 10^6\)
对于所有的测试点，每个测试点分配15.0s的时限和512.0 MB的内存