Putata 和 Budada 正在玩一個新遊戲。在這個遊戲中，Putata 試圖移動到他的目的地，而 Budada 試圖將 Putata 送回他的起點。

有一個包含 $n$ 個頂點和 $m$ 條有向邊的圖。Putata 將從頂點 $1$ 出發，他的目的地是頂點 $n$。Putata 有兩種方式通過每一條邊。第一種方式是步行通過該邊，這將花費 Putata $t_i$ 秒，但他有 $\frac{p_i}{100}$ 的機率被 Budada 發現。如果 Budada 在某條邊上發現了 Putata，他會在 Putata 通過當前邊之後 將 Putata 傳送回頂點 $1$。第二種方式是潛行通過該邊，這將花費 Putata $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