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

你拥有该城市的详细地图，其中包括所有的公交车站。你目前位于车站 $0$，机场位于车站 $1$。你还拥有每辆公交车从起点站出发和到达终点站的完整时刻表。此外，对于每辆公交车，你都知道它按计划运行的概率（相对于司机罢工导致公交车停运）。假设所有这些事件都是相互独立的。也就是说，已知其他公交车是否按计划运行，不会改变某辆特定公交车按计划运行的概率。

如果你在公交车出发时间之前到达，你可以换乘该公交车。但如果你恰好在出发时间到达，你将没有足够的时间上车。你无法提前确认某辆公交车是否会按计划运行——只有当你尝试上车时才会知道。因此，如果两辆或更多的公交车在同一时间从同一个车站出发，你只能尝试乘坐其中一辆。

图 A.1：对应样例输入 1 的公交时刻表。

考虑图 A.1 中所示的公交时刻表。它列出了几条公交线路的起点站、终点站以及出发和到达时间。你在其中一些线路旁边写下了该线路运行的概率。没有写明概率的公交线路有 $100\%$ 的概率运行。你可以尝试乘坐第一辆列出的公交车。如果它运行，它将直接把你送到机场，你就不必担心了。如果它不运行，情况就会变得更棘手。你可以乘坐第二辆列出的公交车前往车站 $2$。它肯定会发车，但你到达时会太晚，赶不上第三辆原本能让你准时到达机场的公交车。第四辆列出的公交车——你可以赶上——实际运行的概率只有 $0.1$。这是一个糟糕的赌注，所以最好留在车站 $0$ 等待第五辆公交车。如果你赶上了它，你可以尝试乘坐第六辆公交车前往机场；如果那辆车没运行，你仍然有机会回到车站 $0$ 并乘坐最后一辆直达机场的公交车。

输入格式

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

输出格式

显示你赶上飞机的概率，假设你采取最优行动策略。你的答案必须精确到 $10^{-6}$ 的绝对误差范围内。

样例

样例输入 1

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

样例输出 1

0.3124

样例输入 2

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

样例输出 2

0.7