M. Fine Trip
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$n$$$ crossings in Bytetown, connected with $$$m$$$ bidirectional roads. The $$$i$$$-th road connects crossings $$$u_i$$$ and $$$v_i$$$, has length of $$$l_i$$$ meters and a cost factor of $$$c_i$$$.

In order to ease the road traffic, a special fine system is used in Bytetown. You can drive with any speed and change the speed whenever you want. However, if the maximum speed during your travel along the road $$$i$$$ is $$$v$$$ meters per second, you should pay $$$v \cdot c_i$$$ dollars fine.

You live near the crossing $$$1$$$ and want to get to the crossing $$$n$$$ in no more than $$$T$$$ seconds. What is the smallest possible fine you will have to pay if you choose the route and the speed for each road optimally?

Input

In the first line of the input there are three numbers $$$n$$$, $$$m$$$ and $$$T$$$ ($$$1 \leq n \leq 2000$$$, $$$1 \leq m \leq 100\,000$$$, $$$1 \leq T \leq 10^9$$$).

The $$$i$$$-th of the next $$$m$$$ lines contains four numbers $$$u_i$$$, $$$v_i$$$, $$$l_i$$$, $$$c_i$$$, describing the $$$i$$$-th edge according to the statement ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$1 \leq l_i, c_i \leq 10^9$$$).

It is guaranteed that it is possible to reach the crossing $$$n$$$ starting at the crossing $$$1$$$.

Output

Print single real number — the smallest possible fine. Your answer will be considered correct if its relative or absolute error doesn't exceed $$$10^{-6}$$$.

Examples
Input
3 3 100
1 3 100 100
1 2 100 24
2 3 100 24
Output
96.0000000000
Input
3 2 10
1 2 9 1
2 3 1 1000
Output
119.8736659610
Input
4 5 9
1 2 6 7
1 3 6 2
2 3 8 7
2 4 3 4
3 4 1 7
Output
4.1478114200