Putata and Budada are playing a new game. In this game, Putata is trying to move to his destination and Budada is trying to return Putata to his starting point.

There is a graph with $n$ vertices and $m$ directed edges. Putata will start on vertex $1$ and his destination is vertex $n$. Putata has two ways to pass each edge. The first way is to walk through the edge and it will take Putata $t_i$ seconds to pass, but he will have $\frac{p_i}{100}$ probability to be discovered by Budada. If Budada discovered Putata on some edge, then he will teleport Putata to vertex $1$ after Putata goes through the current edge. The second way is to sneak through the edge, which will take Putata $c_i$ seconds. By sneaking through the edge, Putata will not be discovered by Budada on this edge.

Please help Putata to calculate the minimum expected time to move to vertex $n$ under his best strategy.

Input

The first line two integers contains $n,m$($1 \leq n,m \leq 10^5$), denoting the number of vertices and the number of edges on the graph.

Each of the following $m$ lines contains five integers $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$), denoting a directed edge from $u_i$ to $v_i$.

Output

Output a real number, denoting the minimum expected time for Putata to move to vertex $n$ under his best strategy. If it is impossible for Putata to get from $1$ to $n$, output $-1$.

Your answer will be considered correct if its relative or absolute error is less than $10^{-6}$. Formally, let your answer be $a$, and the jury's answer be $b$. Your answer will be considered correct if $\frac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$.

Examples

Input 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

Output 1

12.5000000000

Input 2

2 1
2 1 99 99 0

Output 2

-1