Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
Ebishu0309君は駅 5 に到着するのに最短でも 9 単位時間かかりますが、これは K より長いので -1 を出力してください。
入力例3
6 2 8
1
1
1
1
2 4 2 3
5 1 1 2
出力例3
-1
Ebishu0309君は駅 N に行くことができません。
時刻 K までに到着できない場合だけではなく、そもそも電車を使って駅 N まで行けない場合に関しても、-1 を出力してださい。
writer: Ebishu0309