Marching Course

Members of the Kitafuji High School Brass Band convinced their strict coach that they are ready to perform as a marching band at the Moon Light Festival. The festival is a warm-up for the upcoming domestic contest, so the band wants to draw a crowd with its performance.

The festival limits each performance to $P$ minutes. Each team may choose its route freely within the provided area. The area has $N$ checkpoints, numbered 1 through $N$, and $M$ bidirectional roads, each connecting two checkpoints. The band knows the length and the expected number of people along every road. Each team must start at checkpoint 1 and return to checkpoint 1 within $P$ minutes.

If the band marches for $m$ minutes on a road with length $d$ and expected audience $v$, the impression degree is $m \times v / d$. The impression degree of a course is the sum of the impression degrees of all its parts. The band marches at a constant speed of 1 length unit per minute. It may turn around at any time and at any place, including points in the middle of a road. An interval passed two or more times adds to the impression degree each time.

Find the course with the maximum impression degree for a $P$-minute performance.

The first line contains three integers $N$, $M$, and $P$: the number of checkpoints ($2 \le N \le 200$), the number of roads ($N-1 \le M \le N(N-1)/2$), and the performance time ($1 \le P \le 1000$). Each of the following $M$ lines contains four integers $s_i$, $t_i$, $d_i$, $v_i$. Road $i$ connects checkpoints $s_i$ and $t_i$ ($1 \le s_i, t_i \le N$, $s_i \ne t_i$) with length $d_i$ ($1 \le d_i \le 1000$) and expected audience $v_i$ ($1 \le v_i \le 1000$). Any two checkpoints are connected directly or indirectly. No two roads have the same pair of endpoints.

$N$ $M$ $P$

$s_1$ $t_1$ $d_1$ $v_1$

$\ldots$

$s_M$ $t_M$ $d_M$ $v_M$

Print the maximum impression degree of a course for a $P$-minute performance. Answers with an absolute error less than $10^{-4}$ are accepted.