题目描述

前往 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

考虑上图所示的公交计划表。上面列出了几条公交路线的出发地、目的地以及出发时间和到达时间。你在部分公交车计划后面写上了该公交按计划运行的概率。没有写概率的公交车会以 $100\%$ 的概率按计划运行。你可以先尝试第一辆列出的公交车。如果该公交车按计划运行，你便可以直接到达机场，无需担忧。但如果没有，则事情变得复杂起来。假如你上了第二辆公交车，则这辆车一定会出发，但等这辆车到站时你无法赶上第三辆公交车前往机场。你可以上第 $4$ 辆车，但这辆车只有 $0.1$ 的概率启动。所以更好的方案是待在 $0$ 站并乘坐第 $5$ 辆车。如果该车没有出发，你还有机会回到第 $0$ 站并乘坐最后一个公交车直接前往机场。

数据范围与提示

$1 \le m \le 10^6$

$2 \le n \le 10^6$

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

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