Live Mercurian Navigation#12833

Live Mercurian Navigation

1 second
512 megabytes
Hard

In 2121, in Mercury, there are mercurian cities and directed roads between cities. The -th road goes from the a_i-th city to the b_i-th city. For each pair of cities and , there is at most one road from to .

As traffic on Mercury is becoming heavier, the toll of the roads also varies. At time , one should pay (c_i \cdot t + d_i) dollars to travel along the -th road.

Bytica is living in the -st city and would like to go to the -th city, so she uses her oo-car for that. She wants to know the average money she must spend to get from city to city at t \in [0, T].

Note that since mercurian oo-cars are soo fast, traveling on the roads is instant, i.e. it takes no time for Bytica.

Formally, if is the minimum money she should pay to get from city to city at time , Bytica would like to find

\frac{\int_0^{T} f(t) \mathrm{d}t}{T}.

Input

The first line contains integers n, m, T (2 \leq n \leq 10, 1 \leq m \leq n(n - 1), 1 \leq T \leq 10^4).

The -th of the following lines contains integers a_i, b_i, c_i, d_i (1 \leq a_i, b_i \leq n, a_i \neq b_i, 0 \leq c_i, d_i \leq 10^3).

It is guaranteed that Bytica is able to drive from city to city .

Output

Print a real number that denotes the answer. It will be considered correct if its absolute or relative error does not exceed 10^{-6}.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading