问题描述

由于北藤高中管乐团成功地说服了他们严厉的教练，证明了他们的演奏技巧，他们将作为一支行进乐团参加月光音乐节。这个音乐节在吸引即将到来的国内比赛的关注方面是一个序曲。因此，他们希望通过他们的表演吸引音乐节的观众。

尽管这个音乐节将表演时间限制在$P$分钟内，但每个团队可以自由确定他们的表演路线，路线位于一个指定区域内。提供的区域由$N$个检查点组成，编号从$1$到$N$，并且有$M$条双向道路连接两个检查点。北藤管乐团已经获取了每条道路的信息：它的长度和道路两侧预期的人数。每个团队必须从检查点$1$出发，在$P$分钟内返回检查点$1$。为了向音乐节的观众展示北藤管乐团的表演能力，他们严厉的教练想要确定他们的表演路线，以便尽可能多的人听到他们的进行曲。

教练使用“印象度”来确定他们的最佳路线。如果他们在长度为$d$，预期人数为$v$的道路上演奏$m$分钟，那么印象度将为$m \times v / d$。一个路线的印象度是他们在这条路线上表演的印象度之和。行进乐团在行军过程中必须以恒定的速度前进：每分钟前进$1$个单位长度。另一方面，他们可以在任何时间、任何地点包括道路上的一个点处向相反的方向转向。即使他们多次通过相同的区间，印象度也会累积。

你的任务是编写一个程序，以确定具有最大印象度的路线，以便尽可能多地向观众展示北藤管乐团的表演能力。

输入

输入的格式如下。

$N$ $M$ $P$
$s\_1$ $t\_1$ $d\_1$ $v\_1$
$\\ldots$
$s\_M$ $t\_M$ $d\_M$ $v\_M$

第一行包含三个整数$N$，$M$和$P$：检查点的数量$N$（$2 \le N \le 200$），道路的数量$M$（$N-1 \le M \le N(N-1)/2$），以及表演时间$P$（$1 \le P \le 1{,}000$）。接下来的$M$行表示关于道路的信息。其中的第$i$行包含四个整数$s\_i$，$t\_i$，$d\_i$和$v\_i$：第$i$条道路双向连接检查点$s\_i$和$t\_i$（$1 \le s\_i, t\_i \le N$，$s\_i \neq t\_i$），长度为$d\_i$（$1 \le d\_i \le 1{,}000$），预期人数为$v\_i$（$1 \le v\_i \le 1{,}000$）。

你可以假设任意两个检查点之间都直接或间接地通过一条或多条道路连接。你还可以假设不存在有相同端点对的两条道路。

输出

输出一个$P$分钟表演的最大印象度。绝对误差应该小于$10^{-4}$。

示例输入 1

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

### 对示例输入 1 的输出

```plain
6```

* * *

### 示例输入 2

```plain
4 3 9
1 2 2 1
1 3 2 2
1 4 2 3```

### 对示例输入 2 的输出

```plain
13.5```

* * *

### 示例输入 3

```plain
4 3 5
1 2 10 1
2 3 2 100
1 4 3 10```

### 对示例输入 3 的输出

```plain
16.6666666667```

* * *

### 示例输入 4

```plain
3 3 10
1 2 3 1
1 3 4 5
2 3 2 10```

### 对示例输入 4 的输出

```plain
22```