在 ICPCCamp 中，有 $n$ 个城市和 $m$ 条单向道路。 第 $i$ 条道路从第 $a_i$ 个城市通往第 $b_i$ 个城市。 对于每一对城市 $u$ 和 $v$，从 $u$ 到 $v$ 最多只有一条道路。

随着 ICPCCamp 的交通日益繁忙，道路的通行费也在变化。 在时刻 $t$，通过第 $i$ 条道路需要支付 $(c_i \cdot t + d_i)$ 美元。

住在第 $1$ 个城市的 Bobo 想要前往第 $n$ 个城市。 他想知道如果他在 $t \in [0, T]$ 的任意时刻出发，他所需支付的最小费用的平均值是多少。 注意，由于 Bobo 的车速度极快，在道路上行驶不消耗时间。

形式化地说，如果 $f(t)$ 是在时刻 $t$ 从城市 $1$ 到城市 $n$ 所需支付的最小费用，Bobo 想要计算： $$\frac{\int_0^{T} f(t) \mathrm{d}t}{T}$$

输入包含最多 $30$ 组数据。对于每组数据：

第一行包含 $3$ 个整数 $n, m, T$ ($2 \leq n \leq 10, 1 \leq m \leq n(n - 1), 1 \leq T \leq 10^4$)。

接下来的 $m$ 行中，第 $i$ 行包含 $4$ 个整数 $a_i, b_i, c_i, d_i$ ($1 \leq a_i, b_i \leq n, a_i \neq b_i, 0 \leq c_i, d_i \leq 10^3$)。

保证 Bobo 一定能从城市 $1$ 到达城市 $n$。

输出一个浮点数表示答案。 如果答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

样例

输入格式 1

3 3 2
1 2 1 0
2 3 1 0
1 3 1 1

输出格式 1

1.75000000

输入格式 2

3 3 2
1 2 1 0
2 3 1 0
1 3 0 5

输出格式 2

2.00000000