Putata 和 Budada 正在玩一个新游戏。在这个游戏中，Putata 试图移动到他的目的地，而 Budada 试图将 Putata 送回他的起点。

有一个包含 $n$ 个顶点和 $m$ 条有向边的图。Putata 将从顶点 $1$ 出发，他的目的地是顶点 $n$。Putata 有两种方式经过每条边。第一种方式是步行通过这条边，花费 $t_i$ 秒，但会有 $\frac{p_i}{100}$ 的概率被 Budada 发现。如果 Budada 在某条边上发现了 Putata，那么他会在 Putata 通过当前边之后将 Putata 传送回顶点 $1$。第二种方式是潜行通过这条边，花费 $c_i$ 秒。通过潜行，Putata 不会在这条边上被 Budada 发现。

请帮助 Putata 计算在他最优策略下移动到顶点 $n$ 的最小期望时间。

输入格式

第一行包含两个整数 $n,m$（$1 \leq n,m \leq 10^5$），表示图中的顶点数和边数。

接下来 $m$ 行，每行包含五个整数 $u_i, v_i, t_i, p_i, c_i$（$1 \leq u_i,v_i \leq n$, $0 \leq t_i, c_i \leq 10^9$, $0 \leq p_i \leq 99$），表示一条从 $u_i$ 到 $v_i$ 的有向边。

输出格式

输出一个实数，表示 Putata 在他最优策略下移动到顶点 $n$ 的最小期望时间。如果 Putata 无法从 $1$ 到达 $n$，则输出 $-1$。

如果你的答案的相对或绝对误差小于 $10^{-6}$，则视为正确。正式地，设你的答案为 $a$，标准答案为 $b$。当 $\frac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$ 时，你的答案被视为正确。

样例

样例输入 1

4 6
1 2 1 60 10
2 4 9 50 10
2 3 0 99 5
3 2 1 0 10
3 4 3 60 5
1 1 4 51 4

样例输出 1

12.5000000000

样例输入 2

2 1
2 1 99 99 0

样例输出 2

-1