# 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 *a*_{i} − *t**h* city to the *b*_{i} − *t**h* 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^{4}).

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*, *a**i* ≠ *b*_{i}, 0 ≤ *c*_{i}, *d*_{i} ≤ 10^{3}).

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

## Author

ftiasch