5.重建小镇

题目描述

一场地震把$A$住的小镇摧毁了，$A$决心重建家园。$A$已经重建了$n$个家，现在他希望能修建一些道路把它们连接起来。研究地形之后，$A$发现可供修建的道路有$m$条。碰巧的是，其他人最近也成立一个工程队，专门从事修复道路，但他们有自己的计划：工程队关注的是挣钱速度，即总利润和总施工时间的比值。$A$和工程队达成了协议，工程队负责修建道路，将所有牧场连通，而$A$需要支付$f$元。每条道路都有自己的施工时间和建造成本。连接两个相同的牧场的道路可能有多条。保证所有的牧场必定是可连通的，不过也有可能一些道路的建造成本之和会超过$f$。请帮助工程队选择修复哪些道路，才能使单位时间的利润最大？

输入格式

第一行三个整数$n$，$m$，$f$；

第二行到第$m+1$行，第$i+1$行表示第$i$条道路的信息。每行有四个整数$u_i$，$v_i$，$c_i$，$t_i$

$u_i$和$v_i$表示这条道路连接的牧场编号，$c_i$表示修建道路的成本，$t_i$表示道路修建所需要的时间。

输出格式

输出一个保留四位小数的浮点数，表示工程队能挣到的最大单位时间利润，如果工程队无钱可赚，则输出$0.0000$。

数据范围与提示

对于$100\%$的数据，保证$1 \leq u_i,v_i \leq n \leq 400$，$1 < m < 10000$，$1 \leq c_i,t_i,f \leq 2 \times 10^9$。

样例

5 5 100
1 2 20 5
1 3 20 5
1 4 20 5
1 5 20 5
2 3 23 1

1.0625