Putata와 Budada가 새로운 게임을 하고 있습니다. 이 게임에서 Putata는 목적지로 이동하려고 하고, Budada는 Putata를 출발점으로 되돌리려고 합니다.

$n$개의 정점과 $m$개의 방향 간선이 있는 그래프가 있습니다. Putata는 정점 $1$에서 시작하며, 목적지는 정점 $n$입니다. Putata는 각 간선을 통과하는 두 가지 방법이 있습니다. 첫 번째 방법은 간선을 걸어서 통과하는 것으로, 통과하는 데 $t_i$초가 걸리지만, Budada에게 발각될 확률이 $\frac{p_i}{100}$입니다. Budada가 어떤 간선에서 Putata를 발견하면, Putata가 해당 간선을 통과한 후에 정점 $1$로 순간이동시킵니다. 두 번째 방법은 간선을 몰래 통과하는 것으로, $c_i$초가 걸리며, 이 간선에서는 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