In the JSOI Kingdom, everything is taxed, and traveling within the kingdom is no exception. Recently, the JSOI Kingdom's finances have been tight, and King JS has ordered the Minister of Finance, JYY, to quickly submit a tax reform plan to increase the tax revenue collected from people traveling.

Description

The transportation network of the JSOI Kingdom can be viewed as a directed weighted graph with $N$ vertices and $M$ edges. Each vertex in the graph represents a city, and each edge represents a road connecting two cities. There may be multiple roads between the same pair of cities. Each road $i$ has two values, $d_i$ and $c_i$, representing its initial tax and the level of public dissatisfaction incurred by increasing the tax on this road by 1 unit, respectively. The tax of a path is the sum of the taxes of all roads on the path.

King JS wants to increase the tax for traveling from city $s$ to city $t$ as much as possible, but this is not a simple task. The citizens of JSOI are very clever; no matter how you adjust the taxes, they will only take the path from $s$ to $t$ with the minimum total tax. On the other hand, if the tax adjustment causes the total dissatisfaction to exceed a value $P$, it will trigger a social crisis. Therefore, JYY needs to make the tax of the minimum-tax path from $s$ to $t$ as large as possible, provided that the total dissatisfaction incurred does not exceed $P$.

It should be noted that JYY cannot reduce the tax on any road, but he can increase the tax on any road by any real number of units.

Input

The first line contains five integers: $N$, $M$, $P$, $s$, and $t$.

The next $M$ lines each contain four integers: $u_i$, $v_i$, $d_i$, and $c_i$. This describes a directed edge from $u_i$ to $v_i$ with an initial tax of $d_i$ and a dissatisfaction cost of $c_i$ per unit of tax increase.

Output

Output a single real number representing the maximum possible tax for the path from $s$ to $t$. The answer is considered correct if the absolute error is within $10^{-4}$.

Constraints

• For 10% of the data, there is only one path from $s$ to $t$.
• For another 30% of the data, $c_i = 1$.
• For 100% of the data, $1 \le N \le 200$, $1 \le M \le 2 \times 10^4$, $1 \le P \le 10^6$, $1 \le c_i, d_i \le 10$. It is guaranteed that at least one valid path from $s$ to $t$ exists.

Examples

Input 1

3 2 3 1 3
1 2 2 1
2 3 1 2

Output 1

6.000000

Input 2

3 4 5 1 3
1 2 1 2
2 3 1 1
1 3 3 2
1 3 4 1

Output 2

4.250000