问题陈述
由于北富士高中铜管乐队俱乐部的成员成功说服了严厉的教练相信他们的演奏技巧,他们将能够作为军乐队参加月光节。 这个节日是吸引他们参加即将到来的国内比赛的前奏。 因此,他们希望通过他们的表演来吸引节日观众。
虽然这个节日将表演时间限制为 $P$ 分钟,但每个团队都可以在提供的区域自由决定他们的表演路线。 提供的区域由 $N$ 个检查站组成,编号为 $1$ 到 $N$,以及连接两个检查站的 $M$ 双向道路。 Kitafuji Brass Band 已经掌握了每条道路的信息:长度以及路边的预计人数。 每个团队必须从检查点 $1$ 出发,并在 $P$ 分钟内返回检查点 $1$。 为了向音乐节观众展示北藤铜管乐团的演奏能力, 他们严厉的教练希望确定他们的表演路线,以便让更多的人尽可能长时间地聆听他们的进行曲。
教练使用“impression degree“确定他们的最佳路线。 如果他们在长度为 $d$ 且预期人数为 $v$ 的道路上玩 $m$ 分钟, 那么印象度就是$m \times v / d$。 对一门课程的印象度是他们对该课程的表现印象度的总和。 行军乐队在行进过程中必须以恒定速度移动:每 1 美元分钟每 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 的输出
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