H - don't be late /

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