问题描述

给定一个有向图和两个节点$s$和$t$。给定的图中可能包含同一节点对之间的多条边，但不包括自环。每条边$e$都有其初始长度$d_e$和成本$c_e$。你可以通过支付成本来延长一条边。形式上，将边$e$的长度从$d_e$改变为$d_e + x$的成本为$x \cdot c_e$。（注意$x$可以是非整数。）边不能被缩短。

你的任务是通过在成本$P$内延长一些边，使得从节点$s$到节点$t$的最短路径的长度最大化。你可以假设从$s$到$t$至少存在一条路径。

输入

输入由单个测试用例组成，格式如下所示。

$N$ $M$ $P$ $s$ $t$
$v_1$ $u_1$ $d_1$ $c_1$
...
$v_M$ $u_M$ $d_M$ $c_M$

第一行包含五个整数$N$，$M$，$P$，$s$和$t$：$N$ ($2 \leq N \leq 200$)和$M$ ($1\leq M \leq 2{,}000$)分别是给定图中的节点数和边数，$P$ ($0 \leq P \leq 10^6$)是你可以支付的成本限制，$s$和$t$ ($1 \leq s, t \leq N$，$s \neq t$)分别是起始节点和目标路径的结束节点。以下的$M$行中，每行包含四个整数$v_i$，$u_i$，$d_i$和$c_i$，表示从$v_i$到$u_i$（$1 \leq v_i, u_i \leq N$，$v_i \neq u_i$）有一条边，其初始长度为$d_i$（$1 \leq d_i \leq 10$）且成本为$c_i$（$1 \leq c_i \leq 10$）。

输出

输出从节点$s$到节点$t$的最短路径的最大长度，通过在成本$P$内延长一些边。输出结果的绝对或相对误差不超过$10^{-6}$。

示例输入1

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

### 示例输入1的输出

```plain
6.0000000```

---

### 示例输入2

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

### 示例输入2的输出

```plain
2.5000000```

---

### 示例输入3

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

### 示例输入3的输出

```plain
4.2500000```