As Soon As Possible

2 secs 1024 MB
magurofly's icon magurofly

問題文

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

MM 本のバスの情報が与えられます。 バス ii は時刻 Si+0.5S_i + 0.5 に街 AiA_i を出発し、時刻 TiT_i に街 BiB_i に到着します。

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

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

制約

  • 1N,M1051 \le N, M \le 10^5
  • 1Ai,BiN1 \le A_i, B_i \le N
  • 0Si<Ti1090 \le S_i \lt T_i \le 10^9
  • 入力は全て整数である

入力

N MA1 B1 S1 T1AM BM SM TMN\ M\\ A_1\ B_1\ S_1\ T_1\\ \vdots\\ A_M\ B_M\ S_M\ T_M

出力

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

入出力例

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

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

入力例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

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

入力例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

Submit


Go (1.21)