题目描述

AtCoder 共有 $N$ 个城市和 $M$ 条道路。

城市编号为 $1$ 到 $N$，道路编号为 $1$ 到 $M$。 道路 $i$ 双向连接城市 $A_i$ 和城市 $B_i$。

该国在时间 $0$ 达到高峰。如果你从时间 $t$ 开始通过道路 $i$，那么到达另一端需要 $C_i+ \\left\\lfloor \\frac{D_i}{t+1} \\right\\rfloor$ 的时间（$\\lfloor x\\rfloor$ 表示不超过 $x$ 的最大整数）。

高桥计划从城市 $1$ 在时间 $0$ 或稍后的某个整数时间出发前往城市 $N$。

如果高桥可以在每个城市停留一个整数时间单位，请输出高桥可以到达城市 $N$ 的最早时间。根据该问题的约束条件，可以证明答案是一个整数。

如果无法到达城市 $N$，请输出 -1。

约束条件

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq A_i,B_i \leq N$
• $0 \leq C_i,D_i \leq 10^9$
• 输入中的所有值都为整数。

输入

从标准输入读入数据，输入格式如下：

$N$ $M$ $A_1$ $B_1$ $C_1$ $D_1$ $\\vdots$ $A_M$ $B_M$ $C_M$ $D_M$

输出

输出一个整数，表示高桥可以到达城市 $N$ 的最早时间，如果无法到达城市 $N$，则输出 -1。

示例输入1

2 1
1 2 2 3

示例输出1

4

我们首先在城市 $1$ 中停留至时间 $1$。然后，在时间 $1$ 开始，通过道路 $1$，到达城市 $2$ 需要 $2+\\left\\lfloor \\frac{3}{1+1} \\right\\rfloor = 3$ 的时间，所以在时间 $4$ 到达。

无法在时间 $4$ 之前到达城市 $2$。

示例输入2

2 3
1 2 2 3
1 2 2 1
1 1 1 1

示例输出2

3

可能有多条连接同一对城市的道路，以及从一个城市到同一个城市的道路。

示例输入3

4 2
1 2 3 4
3 4 5 6

示例输出3

-1

可能没有从城市 $1$ 到城市 $N$ 的路径。

示例输入4

6 9
1 1 0 0
1 3 1 2
1 5 2 3
5 2 16 5
2 6 1 10
3 4 3 4
3 5 3 10
5 6 1 100
4 2 0 110

示例输出4

20