Putata y Budada están jugando un nuevo juego. En este juego, Putata intenta llegar a su destino y Budada intenta devolver a Putata a su punto de partida.

Hay un grafo con $n$ vértices y $m$ aristas dirigidas. Putata comenzará en el vértice $1$ y su destino es el vértice $n$. Putata tiene dos formas de recorrer cada arista. La primera forma es caminar a través de la arista y le tomará a Putata $t_i$ segundos recorrerla, pero tendrá una probabilidad $\frac{p_i}{100}$ de ser descubierto por Budada. Si Budada descubre a Putata en alguna arista, entonces teletransportará a Putata al vértice $1$ después de que Putata recorra la arista actual. La segunda forma es escabullirse por la arista, lo que le tomará a Putata $c_i$ segundos. Al escabullirse por la arista, Putata no será descubierto por Budada en esta arista.

Por favor, ayuda a Putata a calcular el tiempo esperado mínimo para moverse al vértice $n$ bajo su mejor estrategia.

Entrada

La primera línea contiene dos enteros $n,m$ ($1 \leq n,m \leq 10^5$), que denotan el número de vértices y el número de aristas del grafo.

Cada una de las siguientes $m$ líneas contiene cinco enteros $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$), que denotan una arista dirigida desde $u_i$ hasta $v_i$.

Salida

Imprime un número real, que denote el tiempo esperado mínimo para que Putata se mueva al vértice $n$ bajo su mejor estrategia. Si es imposible que Putata llegue de $1$ a $n$, imprime $-1$.

Tu respuesta se considerará correcta si su error relativo o absoluto es menor que $10^{-6}$. Formalmente, sea tu respuesta $a$ y la respuesta del jurado $b$. Tu respuesta se considerará correcta si $\frac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$.

Ejemplos

Entrada 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

Salida 1

12.5000000000

Entrada 2

2 1
2 1 99 99 0

Salida 2

-1