该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

石老师一天没吃饭了！很急，非常急，迫切的需要吃饭！

徐老师准备给石老师送去一份外卖，拯救石老师！

他们所在的城市有 $n$ 个路口，编号 $1 \sim n$，路口之间一共存在 $m$ 条单向快速路

其中第 $i$ 条快速路可以用 $(u_i,v_i,w_i,x_i,y_i)$ 描述，表示通过这条快速路可以从 $u_i$ 号路口到达 $v_i$ 号路口，需要花费时间为 $w_i$，但是每条快速路都有红绿灯，在红灯时这条快速路无法通过，在绿灯时可以随时通过（特别的，只要徐老师在踏入这条快速路时是绿灯，就算中途变成了红灯，也不影响他通过这条快速路）

为了方便描述，我们用 $x_i,y_i$ 来描述这条快速路的红绿灯，对于当前时刻 $T$，如果 $T \% x_i + y_i < x_i$ 则表示这条快速路在时刻 $T$ 是绿灯，不满足条件则是红灯（这里假设不存在黄灯）

当然，徐老师如果想通过某条快速路，但是此时这条快速路是红灯无法通过，徐老师可以在 $u_i$ 处等待，等到绿灯后通过这条快速路。

现在徐老师想知道，如果他从 $1$ 号路口出发，此时时刻为 $0$，最短在什么时间可以到达石老师所在的 $n$ 号路口？

输入格式

输入第一行包含两个整数 $n,m$，含义如题

接下来 $m$ 行，每行包含五个整数 $u_i,v_i,w_i,x_i,y_i$ 描述这条单向快速路

输出格式

输出徐老师最快到达石老师处的时刻

数据范围

对于 $20\%$ 的数据，$n,m,x_i,y_i \leq 10$

对于 $40\%$ 的数据，$n,m,x_i,y_i \leq 100$

对于 $60\%$ 的数据，$n,m,w_i,x_i,y_i \leq 1000$

对于另外 $20\%$ 的数据，$y_i = 0$

对于 $100\%$ 的数据，$1 \leq n \leq 10^5, 1 \leq m \leq 10^6, 0 \leq y_i < x_i \leq 10^4, 0 \leq w_i \leq 10^4$

题目保证有解

样例输入1

5 7
1 2 7 3 1
1 4 4 2 0
2 3 5 4 1
2 4 6 3 2
3 4 4 2 1
4 3 3 3 0
4 5 2 5 4

样例输出1

7

样例解释1

在 $1$ 号路口时 $T = 0$ 时刻，满足 $0\% 2 + 0 < 2$，沿 $1\to 4$ 走到 $4$ 号路口，此时来到 $T = 0+4=4$ 时刻

在 $4$ 号路口，此时 $4 \to 5$ 的快速路为红灯，需要等待

在 $4$ 号路口等待 $1$ 个单位时间等到 $T = 5$ 时刻，满足 $5\%5+4 < 5$，沿 $4\to 5$ 走到 $5$ 号路口，此时来到 $T=5+2=7$ 时刻

这是最快到达 $5$ 号路口的方案，到达时刻为 $T = 7$