有一个有$n$个点和$m$条边的有向无环图。每条边形如$(u,v,w,x)$，其中$u$，$v$表示这条边的起点终点，$w$表示经过这条边花费的时间，$x$表示这条边的权重。图可能有重边。开始时你在$1$号点，每当你到达一个点的时候，你会按照该点出边的权重随机选一条边花费边对应的时间走过去。具体来说，对于一个点$u$，假如有$k$个起点为该点的边，它们的权重分别为$x_1,x_2,x_3...x_k$，那么选择第$i$个边的概率就是$\frac{x_i}{\sum_{j=1}^{k}x_j}$。你的目的是在$L$单位时间内到达一个出度为$0$的点。当然你可以在到达某一个点时重新开始，如果你重新开始，你就能回到$1$号点并重新开始（即从$0$时刻开始），且无次数限制。你需要最小化你的总时间，即包括重新开始之前花费的时间。当然在你运气足够好的情况下，你一定可以达成目标。保证一定有至少一条以$1$号地点为起点的边。请阅读样例以更清晰地理解题意。

输入格式

第一行三个正整数$n$，$m$，$L$。

接下来$m$行，每行四个正整数$u$，$v$，$w$，$x$。

输出格式

一行一个浮点数表示答案，令你的答案为$a$，标准答案为$b$，如果满足$\frac{|a-b|}{max(1,b)} \leq 10^{-9}$（即绝对误差或者相对误差不超过$10^{-9}$）即为正确。

样例一

input

3 2 3
1 2 2 1
1 2 4 1

output

6

explanation

设答案为$Ans$。

则$Ans=\frac{1}{2}\times 2+\frac{1}{2}\times(Ans+4)$。

即有一半的可能性你可以直接完成，否则你需要重新开始并再来一次。

解得$Ans=6$。

样例二

input

4 4 7
1 2 2 7
1 3 4 6
2 4 6 3
3 4 3 2

output

9.3333333333

样例三

input

5 7 12
1 3 5 5
4 5 7 9
2 5 8 1
3 5 4 4
1 2 3 3
3 4 3 1
2 4 2 5

output

11.3571428571

样例四

见下发文件

限制与约定

本题共有$25$个测试点，每个测试点$4$分。

对于全部数据$2\leq n\leq 100$，$1\leq m\leq 200$，$1\leq w,x\leq 100$，$0\leq L\leq 10^9$，保证输入的图无环，答案$\leq 10^9$，保证至少存在一条从$1$出发走到出度为$0$的点长度$\leq L$的路径。

具体数据规模请见下表。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载