1137 : Toll

Description

In ICPCCamp, there are n cities and m unidirectional roads between cities. The i-th road goes from the a_i − th city to the b_i − 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 (c_i ⋅ t + d_i) 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 ≤ 10⁴).

The i-th of the following m lines contains 4 integers a_i, b_i, c_i, d_i(1 ≤ a_i, b_i ≤ n, ai ≠ b_i, 0 ≤ c_i, d_i ≤ 10³).

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

Hint

Source

Author

ftiasch