Bytetown 有 $n$ 个路口，由 $m$ 条双向道路连接。第 $i$ 条道路连接路口 $u_i$ 和 $v_i$，长度为 $l_i$ 米，费用系数为 $c_i$。

为了缓解交通压力，Bytetown 实行了一种特殊的罚款制度。你可以以任意速度行驶，并随时改变速度。然而，如果你在通过第 $i$ 条道路时的最大速度为 $v$ 米/秒，则需要支付 $v \cdot c_i$ 美元的罚款。

你住在路口 1 附近，想要在不超过 $T$ 秒的时间内到达路口 $n$。如果你能最优地选择路线以及每条道路上的速度，那么你需要支付的最小罚款是多少？

输入格式

输入的第一行包含三个数字 $n, m$ 和 $T$ ($1 \le n \le 2000, 1 \le m \le 100\,000, 1 \le T \le 10^9$)。

接下来的 $m$ 行中，第 $i$ 行包含四个数字 $u_i, v_i, l_i, c_i$，描述了第 $i$ 条边 ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le l_i, c_i \le 10^9$)。

保证从路口 1 出发能够到达路口 $n$。

输出格式

输出一个实数，表示最小可能的罚款。如果你的答案与标准答案的相对误差或绝对误差不超过 $10^{-6}$，则被视为正确。

样例

样例输入 1

3 3 100
1 3 100 100
1 2 100 24
2 3 100 24

样例输出 1

96.0000000000

样例输入 2

3 2 10
1 2 9 1
2 3 1 1000

样例输出 2

119.8736659610

样例输入 3

4 5 9
1 2 6 7
1 3 6 2
2 3 8 7
2 4 3 4
3 4 1 7

样例输出 3

4.1478114200