행진 코스

키타후지 고등학교 브라스 밴드부 부원들이 엄격한 코치를 설득해, 달빛 축제에서 행진 연주를 하게 되었다. 이 축제는 곧 열릴 국내 대회를 앞둔 준비 무대다. 그래서 밴드는 연주로 축제 관객을 끌어모으려 한다.

축제는 연주 시간을 최대 $P$분으로 제한한다. 각 팀은 주어진 지역 안에서 연주 코스를 자유롭게 정할 수 있다. 이 지역에는 1번부터 $N$번까지 번호가 붙은 체크포인트 $N$개와, 두 체크포인트를 양방향으로 잇는 도로 $M$개가 있다. 밴드는 각 도로의 길이와 도로변의 예상 관객 수를 알고 있다. 각 팀은 체크포인트 1에서 출발해 $P$분 안에 체크포인트 1로 돌아와야 한다.

길이가 $d$인 도로를 $m$분 동안 연주하고 예상 관객이 $v$명이면 인상도는 $m \times v / d$이다. 코스의 인상도는 코스의 각 구간 인상도를 모두 더한 값이다. 밴드는 분당 1 단위 길이의 일정한 속도로 행진한다. 도로 중간의 점을 포함해 언제 어디서든 방향을 돌릴 수 있다. 같은 구간을 두 번 이상 지나면 그때마다 인상도가 누적된다.

$P$분 연주에서 인상도가 최대가 되는 코스를 구하라.

첫 줄에는 세 정수 $N$, $M$, $P$가 주어진다. 각각 체크포인트 수($2 \le N \le 200$), 도로 수($N-1 \le M \le N(N-1)/2$), 연주 시간($1 \le P \le 1000$)이다. 이어지는 $M$개의 줄에는 네 정수 $s_i$, $t_i$, $d_i$, $v_i$가 주어진다. 도로 $i$는 체크포인트 $s_i$와 $t_i$를 잇고($1 \le s_i, t_i \le N$, $s_i \ne t_i$), 길이는 $d_i$($1 \le d_i \le 1000$), 예상 관객 수는 $v_i$($1 \le v_i \le 1000$)이다. 임의의 두 체크포인트는 직접 또는 간접적으로 연결되어 있다. 같은 두 끝점을 가진 도로는 없다.

$N$ $M$ $P$

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

$\ldots$

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

$P$분 연주에서 얻을 수 있는 최대 인상도를 출력한다. 절대 오차가 $10^{-4}$보다 작으면 정답으로 인정한다.