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
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 .
Print a real number that denotes the answer. It will be considered correct if its absolute or relative error does not exceed 10^{-6}.
Example 1
Example 2