题目描述

有一个城市，可以描述为 $n$ 个点 $m$ 条边的无向图,每个点是一个路口, 每条边是一条道路。

现在有一个乐队要在这个城市中表演，从 $1$ 号点出发,最多表演 $P$ 分钟后回到 $1$ 号点。

第 $i$ 条边有两个参数 $d$ 和 $v$ ，表示道路长度和该道路上的观看人数。

如果在第某条长度为 $d$ 和观看人数为 $v$ 的道路上表演 $t$ 分钟，那么受欢迎程度会增加 $v\times t/d$。(初始时受欢迎程度为0)

这个乐队是一边行进一边表演的, 行进速度为每分钟 $1$ 个单位距离。但是，乐队可以在任意时候任意位置转向,包括道路中间的任意点。

现在你想知道,在 $P$ 分钟的表演时间内，能得到的最大受欢迎程度是多少。

输入格式

第一行三个整数 $n,m,P$ ，表示点数，边数和表演总时间。 下面 $m$ 行，第 $i+1$ 行四个数 $s_i,z_t,d_i,v_i$ ，表示第 $i$ 条道路的信息。

输出格式

一行，一个实数，四舍五入保留 $3$ 位小数，表示答案。

3 3 4
1 2 1 1
2 3 2 4
3 1 1 1

6.000

4 3 9
1 2 2 1
1 3 2 2
1 4 2 3

13.500

说明

对于 $100\%$ 的数据， $n\leq 200,m\leq n(n-1)/2,1\leq v_i,d_i,P\leq1000$ 。