给定一个有向图以及两个节点 $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$：$N$ ($2 \le N \le 200$) 和 $M$ ($1 \le M \le 2,000$) 分别是给定图的节点数和边数，$P$ ($0 \le P \le 10^6$) 是你可以支付的成本上限，$s$ 和 $t$ ($1 \le s, t \le N, s \neq t$) 分别是目标路径的起点和终点。接下来的 $M$ 行，每行包含四个整数 $v_i, u_i, d_i$ 和 $c_i$，表示存在一条从 $v_i$ 到 $u_i$ 的边（$1 \le v_i, u_i \le N, v_i \neq u_i$），其初始长度为 $d_i$ ($1 \le d_i \le 10$)，单位长度延长成本为 $c_i$ ($1 \le c_i \le 10$)。

输出格式

输出在总成本不超过 $P$ 的前提下，通过延长某些边所能达到的从 $s$ 到 $t$ 的最短路径的最大长度。输出的绝对误差或相对误差不超过 $10^{-6}$ 即可。

样例

样例输入 1

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

样例输出 1

6

样例输入 2

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

样例输出 2

2.5000000

样例输入 3

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

样例输出 3

4.25