この世界には 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)

入力例1

3 2 8
2
1 2 3 4
2 3 1 2

出力例1

7

• 駅 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 を出力してださい。