高峰时段 2

题目描述

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$ 的最大整数。）

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

如果他可以在每个城市停留整数个单位时间，求高桥君最早到达城市 $N$ 的时间。可以证明，在本问题的约束下答案是整数。

如果城市 $N$ 不可达，输出 -1。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

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

样例

2 1
1 2 2 3

4

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

不可能早于时间 4 到达城市 2。

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

3

可能存在多条连接同一对城市的道路，也可能存在从城市通向自身的道路。

4 2
1 2 3 4
3 4 5 6

-1

可能不存在从城市 1 到城市 $N$ 的路径。

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

20

数据范围

• $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$
• 输入均为整数