Description

你的飞机即将起飞去参加 ICPC 总决赛，而去机场的唯一方式是乘坐公交车。不幸的是，一些公交车司机正在考虑罢工，所以你不知道是否能按时到达机场。你的目标是规划你的行程，以最大化赶上飞机的概率。

你有一张城市的详细地图，包括所有的公交车站。你现在在车站 $0$，机场在车站 $1$。你还有一份完整的公交车时刻表，记录了每辆公交车从起始站出发和到达目的站的时间。此外，对于每辆公交车，你知道它按计划运行的概率，而不是司机罢工导致公交车停运。假设所有这些事件是独立的。也就是说，某辆公交车按计划运行的概率不会因为你知道其他公交车是否按计划运行而改变。

如果你在公交车出发时间之前到达，你可以转乘那辆公交车。但如果你正好在出发时间到达，你将没有足够的时间上车。你无法提前验证某辆公交车是否按计划运行——只有当你尝试上车时才会知道。所以如果两辆或更多公交车在同一时间离开一个车站，你只能尝试上其中一辆。

考虑图 A.1 中显示的公交车时刻表。它列出了几条公交线路的起始站和目的站以及出发和到达时间。你在其中一些旁边写下了该线路运行的概率。没有写概率的公交线路有 $100\%$ 的运行概率。你可以尝试赶上第一辆列出的公交车。如果它按计划运行，它会直接带你到机场，你就可以不再担心。如果没有，事情就会变得更加棘手。你可以乘坐第二辆列出的公交车到车站 $2$。它肯定会出发，但你会太晚而赶不上第三辆列出的公交车，否则它会按时把你送到机场。第四辆列出的公交车——你可以赶上——实际上只有 $0.1$ 的运行概率。这是一个糟糕的选择，所以最好留在车站 $0$ 等待第五辆列出的公交车。如果你赶上了它，你可以尝试搭乘第六辆列出的公交车去机场；如果那辆车不运行，你仍然有机会返回车站 $0$ 并赶上最后一辆直达机场的公交车。

Input Format

输入的第一行包含两个整数 $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 < n, a eq b)$，表示公交车的起始站和目的站。接下来是整数 $s$ 和 $t (0 \le s < t \le k)$，给出从车站 $a$ 出发和到达车站 $b$ 的时间。行的最后一个值是 $p (0 \le p \le 1$，小数点后最多有 $10$ 位)，表示公交车按计划运行的概率。

Output Format

显示你赶上飞机的概率，假设你遵循最佳行动方案。你的答案必须在绝对误差 $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

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

0.7

Hint

时间限制：10 秒，内存限制：1024 MB。

特别裁判提供者：

题面翻译由 ChatGPT-4o 提供。