Putata и Budada играют в новую игру. В этой игре Putata пытается добраться до своего пункта назначения, а Budada пытается вернуть Putata в начальную точку.

Дан граф с $n$ вершинами и $m$ ориентированными рёбрами. Putata начинает движение из вершины $1$, а его пункт назначения — вершина $n$. У Putata есть два способа пройти каждое ребро. Первый способ — пройти ребро пешком, это займёт $t_i$ секунд, но с вероятностью $\frac{p_i}{100}$ он будет обнаружен Budada. Если Budada обнаружит 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