AT_tkppc4_1_h don't be late

[problemUrl]: https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_h この世界には $ 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 $ に到着することができるのか判定し、できるのならば最も早い時刻はいつなのか求めてください。

入力は以下の形式で標準入力から与えられます。 > $ 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 $ と出力してください。

### 制約 - 入力は全て整数である。 - $ 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\ (1\ \leq\ i\ \leq\ M) $ ### Sample Explanation 1 以下のように動けば、時刻 $ 7 $ に目的地の駅 $ 3 $ に到着することができます。 - 駅 $ 1 $ を時刻 $ 0 $ に出発する。$ 1 $ 本目の路線を使って、駅 $ 2 $ に移動する。 - 駅 $ 2 $ に時刻 $ 3 $ に到着する。 - 駅 $ 2 $ での乗換に $ 2 $ 単位時間かかる。時刻 $ 5 $ に乗換が完了する。 - 駅 $ 2 $ を時刻 $ 6 $ に出発する。$ 2 $ 本目の路線を使って、駅 $ 3 $ に移動する。 - 駅 $ 3 $ に時刻 $ 7 $ に到着する。 ### Sample Explanation 2 Ebishu0309君は駅 $ 5 $ に到着するのに最短でも $ 9 $ 単位時間かかりますが、これは $ K $ より長いので $ -1 $ を出力してください。 ### Sample Explanation 3 Ebishu0309君は駅 $ N $ に行くことができません。 時刻 $ K $ までに到着できない場合だけではなく、そもそも電車を使って駅 $ N $ まで行けない場合に関しても、$ -1 $ を出力してださい。