题目描述

前往 ICPC Finals 的飞机即将起飞，并且唯一的前往机场的方式是公交车。不幸运的是，一部分公交车司机正在罢工，所以你无法确定是否能及时赶往机场。你的目标是规划你的行程来最大化赶上飞机的概率。

你有一张非常详细的地图，地图上列有所有的公交车站。你在编号为 $0$ 的车站，而机场在编号为 $1$ 的车站，并且你知道每辆公交车的出发时间和到达时间，以及公交车按计划运行的概率（因为公交车司机可能会罢工）。假设各个公交车的罢工事件之间条件无关，也就是说，对于任何一辆公交车，即使你知道其它的公交车是否按计划运行，该公交车按计划运行的概率也不会改变。

如果你在出发时间前到达了起点站，你便可以坐上那辆车。但如果你在出发时间时恰好到达了起点站，你就没有足够的时间上车。你无法提前预知公交车是否会按计划运行——在上车后才能判断。也就是说，如果有多辆车在同一时间出发，你只能尝试上其中的一辆车。

输入格式

第一行有两个整数 $m (1 \le m \le 10^6)$ 和 $n (2 \le n \le 10^6)$，分别表示公交车的数量和车站的数量。

接下来一行有一个整数 $k (1 \le k \le 10^{18})$，表示你必须到达机场的时间。

接下来 $m$ 行每行描述一个公交车。每行有两个整数 $a,b (0 \le a,b \lt n,a \neq b)$，分别表示公交车的起点站和目的地。接下来两个整数 $s,t (0 \le s \lt t \le k)$，表示从车站 $a$ 的出发时间和到达车站 $b$ 的时间。最后为一个实数 $p (0 \le p \le 1)$，小数点后不超过 $10$ 位，表示公交车按计划运行的概率。

输出格式

输出最优策略下赶上飞机的概率。你的答案的绝对误差不能超过 $10^{-6}$.

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

0.3124

数据范围与提示

$1 \le m \le 10^6$

$2 \le n \le 10^6$

$1 \le k \le 10^{18}$

在不侵犯原题版权的情况下，本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布，注明出处时需指向本题链接。