Архипелаг состоит из n островов, между которыми ходят паромы по расписанию.

Каждый маршрут парома задаётся пятью числами u v d p t:

• паром отправляется с острова u на остров v;
• первое отправление происходит в момент времени d;
• далее паром отправляется каждые p минут, то есть в моменты d, d + p, d + 2*p, ...;
• время в пути равно t минут.

Путешественник находится на острове 1 в момент времени 0 и хочет как можно раньше добраться до острова n.

На любом острове можно ждать сколько угодно. Если путешественник прибыл на остров в момент времени, не превышающий время отправления парома, он может сесть на этот паром.

Требуется определить минимально возможное время прибытия на остров n. Если добраться невозможно, выведите -1.

Входные данные

Первая строка содержит два целых числа n и m — количество островов и количество маршрутов паромов.

Каждая из следующих m строк содержит пять целых чисел u, v, d, p, t, описывающих один маршрут парома.

Ввод осуществляется из стандартного ввода.

Выходные данные

Выведите одно целое число:

• минимальное время прибытия на остров n, если это возможно;
• -1, если добраться нельзя.

Вывод осуществляется в стандартный вывод.

Ограничения

• 2 <= n <= 100000
• 0 <= m <= 200000
• 1 <= u, v <= n
• 0 <= d < p
• 1 <= p <= 1000
• 1 <= t <= 100000

Примеры

Пример 1

Входные данные

2 1
1 2 0 1 1

Выходные данные

1

Пример 2

Входные данные

3 3
1 2 0 5 10
2 3 1 2 3
1 3 4 7 20

Выходные данные

14