MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

You are given a directed graph and two nodes $s$ and $t$. The given graph may contain multiple edges between the same node pair but not self loops. Each edge $e$ has its initial length $d\_e$ and the cost $c\_e$. You can extend an edge by paying a cost. Formally, it costs $x \\cdot c\_e$ to change the length of an edge $e$ from $d\_e$ to $d\_e + x$. (Note that $x$ can be a non-integer.) Edges cannot be shortened.

Your task is to maximize the length of the shortest path from node $s$ to node $t$ by lengthening some edges within cost $P$. You can assume that there is at least one path from $s$ to $t$.

Input

The input consists of a single test case formatted as follows.

$N$ $M$ $P$ $s$ $t$
$v\_1$ $u\_1$ $d\_1$ $c\_1$
...
$v\_M$ $u\_M$ $d\_M$ $c\_M$

The first line contains five integers $N$, $M$, $P$, $s$, and $t$: $N$ ($2 \\leq N \\leq 200$) and $M$ ($1\\leq M \\leq 2{,}000$) are the number of the nodes and the edges of the given graph respectively, $P$ ($0 \\leq P \\leq 10^6)$ is the cost limit that you can pay, and $s$ and $t$ ($1 \\leq s, t \\leq N$, $s \\neq t$) are the start and the end node of objective path respectively. Each of the following $M$ lines contains four integers $v\_i$, $u\_i$, $d\_i$, and $c\_i$, which mean there is an edge from $v\_i$ to $u\_i$ ($1 \\leq v\_i, u\_i \\leq N$, $v\_i \\neq u\_i$) with the initial length $d\_i$ ($1 \\leq d\_i \\leq 10$) and the cost $c\_i$ ($1 \\leq c\_i \\leq 10$).

Output

Output the maximum length of the shortest path from node $s$ to node $t$ by lengthening some edges within cost $P$. The output can contain an absolute or a relative error no more than $10^{-6}$.

Sample Input 1

3 2 3 1 3
1 2 2 1
2 3 1 2```

### Output for the Sample Input 1

```plain
6.0000000```

* * *

### Sample Input 2

```plain
3 3 2 1 3
1 2 1 1 
2 3 1 1
1 3 1 1```

### Output for the Sample Input 2

```plain
2.5000000```

* * *

### Sample Input 3

```plain
3 4 5 1 3
1 2 1 2
2 3 1 1
1 3 3 2
1 3 4 1```

### Output for the Sample Input 3

```plain
4.2500000```

* * *