CSG-CPC
Online Judge

# 1137 : Toll

Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 1     Solved: 1     SpecialJudge

## Description

In ICPCCamp, there are n cities and m unidirectional roads between cities. The i-th road goes from the ai − th city to the bi − th city. For each pair of cities u and v, there is at most one road from u to v.

As traffic in ICPCCamp is becoming heavier, toll of the roads also varies. At time t, one should pay (ci ⋅ t + di) dollars to travel along the i-th road.

Bobo living in the 1-st city would like to go to the n-th city. He wants to know the average money he must spend at least if he starts from city 1 at t ∈ [0, T]. Note that since Bobo’s car is super-fast, traveling on the roads costs him no time. Formally, if f(t) is the minimum money he should pay from city 1 to city n at time t, Bobo would like to find

$$\int_{0}^{T}\frac{f(t)dt}{T}$$

## Input

The first line contains 3 integers n, m, T(2 ≤ n ≤ 10, 1 ≤ m ≤ n(n − 1), 1 ≤ T ≤ 104).

The i-th of the following m lines contains 4 integers ai, bi, ci, di(1 ≤ ai, bi ≤ n, ai ≠ bi, 0 ≤ ci, di ≤ 103).

It is guaranteed that Bobo is able to drive from city 1 to city n.

## Output

A floating number denotes the answer. It will be considered correct if its absolute or relative error does not exceed 10 − 6.

## Sample

3 3 2
1 2 1 0
2 3 1 0
1 3 1 1
3 3 2
1 2 1 0
2 3 1 0
1 3 0 5
1.75000000
2.00000000

ftiasch