Longest Shortest Path

You are given a directed graph and two vertices $s$ and $t$. The graph can hold several edges between the same ordered pair of vertices, but it has no self loop.

Every edge $e$ has an initial length $d_e$ and a unit price $c_e$. Paying $x \cdot c_e$ changes the length of $e$ from $d_e$ to $d_e + x$. Here $x$ is a real number that is at least 0, and it does not have to be an integer. An edge cannot be shortened.

Lengthen some edges so that the total payment is at most $P$, and make the shortest path from $s$ to $t$ as long as possible. At least one path from $s$ to $t$ exists.

The input is a single test case in the following format.

N M P s t
v1 u1 d1 c1
...
vM uM dM cM

The first line holds five integers $N$, $M$, $P$, $s$, and $t$. $N$ ($2 \le N \le 200$) is the number of vertices, $M$ ($1 \le M \le 2000$) is the number of edges, $P$ ($0 \le P \le 10^6$) is the budget you may spend, and $s$ and $t$ ($1 \le s, t \le N$, $s \ne t$) are the start and the end vertex of the path.

Each of the next $M$ lines holds four integers $v_i$, $u_i$, $d_i$, and $c_i$. There is an edge from $v_i$ to $u_i$ ($1 \le v_i, u_i \le N$, $v_i \ne u_i$) whose initial length is $d_i$ ($1 \le d_i \le 10$) and whose unit price is $c_i$ ($1 \le c_i \le 10$).

Print, on one line, the largest length of the shortest path from $s$ to $t$ that you can reach by lengthening edges within the budget $P$.

Round the value at the eighth digit after the decimal point and print exactly seven digits after the decimal point, padded with zeros. A value that falls exactly halfway rounds up.