北富士高中的管乐团成员成功说服了严厉的教练，他们将作为行进管乐团参加月光节。这次节日是他们为即将到来的国内比赛展示风采的序曲。因此，他们希望通过表演吸引节日观众。

尽管节日将表演时间限制在 $P$ 分钟以内，但每个团队可以自由决定他们在指定区域内的表演路线。该区域由 $N$ 个检查点（编号为 $1$ 到 $N$）和连接两个检查点的 $M$ 条双向道路组成。北富士管乐团已经掌握了每条道路的信息：道路长度以及路边预期的观众人数。每个团队必须从检查点 $1$ 出发，并在 $P$ 分钟内回到检查点 $1$。为了向节日观众展示北富士管乐团的表演能力，严厉的教练希望确定他们的表演路线，以便尽可能多的人在尽可能长的时间内听到他们的演奏。

教练使用“印象分”来确定他们的最佳路线。如果他们在长度为 $d$、预期观众人数为 $v$ 的道路上演奏了 $m$ 分钟，那么印象分为 $m \times v / d$。一条路线的印象分是他们在该路线上表演的印象分之和。行进管乐团在行进时必须保持恒定速度：每分钟 $1$ 个单位长度。另一方面，他们可以在任何时间、任何地点（包括道路上的某一点）掉头。即使他们多次经过同一路段，印象分也会累积。

你的任务是编写一个程序，确定一条印象分最高的路线，以便尽可能多地向观众展示北富士管乐团的表演能力。

输入格式

第一行包含三个整数 $N$、$M$ 和 $P$：检查点的数量 $N$ ($2 \le N \le 200$)，道路的数量 $M$ ($N - 1 \le M \le N(N - 1)/2$)，以及表演时间 $P$ ($1 \le P \le 1000$)。接下来的 $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 1000$)，预期观众人数为 $v_i$ ($1 \le v_i \le 1000$)。

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

输出格式

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

样例

输入 1

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

输出 1

6

输入 2

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

输出 2

13.5

输入 3

4 3 5
1 2 10 1
2 3 2 100
1 4 3 10

输出 3

16.6666666667

输入 4

3 3 10
1 2 3 1
1 3 4 5
2 3 2 10

输出 4

22