As Soon As Possible

2 secs 1024 MB
magurofly

問題文


MojaCoder国には ヶ所の街があり、これらの街の間にはバスが走っています。 あなたはこれから街 を出発し、街 まで行こうとしています。

本のバスの情報が与えられます。 バス は時刻 に街 を出発し、時刻 に街 に到着します。

時刻 に街 を出発するとき、街 に到着するのは可能か判定し、可能なら最速の到着時刻を答えてください。

なお、バスの乗り降りにかかる時間は無視します。

制約


  • 入力は全て整数である

入力


出力


に到着することが可能な場合は到着時間、不可能なら を出力せよ。

入出力例


入力例1
2 2
1 2 1 9
1 2 2 3
出力例1
3

バス に乗ることで、時刻 に到着します。 バス が先に来ますが、後に来るバス に乗ったほうが早いです。

入力例2
5 8
1 2 0 2
2 3 2 4
3 4 6 7
4 2 0 1
1 4 1 3
2 5 0 2
3 3 1 3
3 5 2 8
出力例2
-1

から街 へは行くことができません。

入力例3
3 6
1 2 0 4
1 2 1 2
1 2 1 3
1 3 0 7
2 3 3 5
2 3 4 6
出力例3
5

提出


Go (1.14)