配点 : 400 点
問題文
在这个世界上
有 N 个站,并且该站
它的编号为 1, 2, 3, ..., N 。车站 i (2 \leq i \leq N-1) 现在,我们转接吧。 t_i 需要单位时间。
另外,连接车站的线路是 M 书籍可用,i 主要路线如下。
- 駅 a_i 从车站 双向连接 b_i 。
- 駅 a_i 和车站 沿此路线在 b_i 之间行驶 c_i 需要单位时间。请注意,任一方向的行程时间都保持相同。
- 在此线路上,火车向任一方向行驶 火车仅在 d_i 倍数的时间发车。
好吧,Ebishu0309 睡过头了。当前时间是 0 他在车站
我在 1 。
他是一个站
我想我应该去 N 。车站
我不知道我是否可以去 N ,但如果可以的话,时间
我正在考虑去 K 。
他是时候了 直到 K (时间 K 仅包括)到车站 确定您是否可以到达 N ,如果可以,最早的时间是多少。
制約
- 所有输入均为整数。
- 2 \leq N \leq 2\times10^5
- 1 \leq M \leq 2\times10^5
- 1 \leq K \leq 10^{12}
- 1 \leq t_i \leq 10^9 (2 \leq i \leq N-1)
- 1 \leq a_i , b_i \leq N (1 \leq i \leq M, a_i ≠ b_i)
- 1 \leq c_i < d_i \leq 10^9 (1 \leq i \leq M)
入力
输入是按以下格式从标准输入给出的。 逐行打印
N M K
t_2
\vdots
t_{N-1}
a_1 b_1 c_1 d_1
\vdots
a_M b_M c_M d_M
出力
Ebishu0309 你是时候了 K 车站前
如果可以到达 N ,请设置该时间。
在 1 行上输出。
如果不可能,-1 。
入力例1
3 2 8
2
1 2 3 4
2 3 1 2
出力例1
7如果您按如下方式移动,则时间 7 到目的地站 您可以到达 3 。
- 駅 1 到时间 从 0 出发。1 使用干线到达车站。 转至 2 。 时间在
- 駅 2 到达 3 。 转帐至
- 駅 2 转乘于 2 需要单位时间。时间 转账已于 5 完成。
- 駅 2 到时间 从 6 出发。2 使用干线到达车站。 转至 3 。 时间在
- 駅 3 到达 7 。 转帐至
入力例2
5 5 8
2
1
2
1 2 2 3
1 3 2 3
2 5 4 5
3 4 1 2
4 5 1 3
出力例2
-1
惠美州0309君洼站 最早到达 5 在最短的时间内到达 9 需要单位时间,但是这个 K 因为它长于 我无法前往 -1 。
入力例3
6 2 8
1
1
1
1
2 4 2 3
5 1 1 2
出力例3
-1
惠美州0309君洼站
最早到达 N 。
時刻 K 不仅如果您无法通过
即使您无法前往 N ,
请输出-1 。
作者: 惠美州0309