Mr. Whitacre is having a lot of fun assaying with his choir. However, it is a bit late and he will have to go home sooner or later. Furthermore, it is starting to snow and the streets are getting worse by the minute. How much time can Mr. Whitacre enjoy before departing?

Let us model the city
as an undirected graph with n vertices (street crosses, numbered from 0)
and m edges (streets).
Mr. Whitacre is currently at vertex 0, and he has to reach vertex n−1 (home).
The cost to traverse each street i is a_{i} t + b_{i},
where t denotes the time when Mr. Whitacre starts traversing that street.
For instance, if he starts walking that street right now,
the time to traverse it is just b_{i}.
Mr. Whitacre must be at home at most at time T.

Input

Input is all integer numbers,
and consists of several cases,
each with n, m and T,
followed by the information of the m streets x_{i} y_{i} a_{i} b_{i}.
Assume 2 ≤ n ≤ 10^{4},
0 ≤ m ≤ 5n,
1 ≤ T ≤ 10^{6},
x_{i} ≠ y_{i},
that between two vertices there is no more than one edge,
and that a_{i} and b_{i} are between 0 and 1000.

Output

For every case, print the maximum choir assay time with three digits after the decimal point. If it is impossible to reach home at time T, print “impossible”. The input cases have no precision issues.

Public test cases

**Input**

2 1 10 0 1 2 3 3 1 1000 1 2 0 0 5 5 100 4 0 10 0 0 3 2 10 2 4 1 5 4 3 1 20 3 2 0 10

**Output**

2.333 impossible 10.000

Information

- Author
- Damià Torres
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Setzè Concurs de Programació de la UPC - Final
- Date
- 2018-09-19