시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 26 | 18 | 18 | 81.818% |
大学生の JOI 君はバスで通学している.JOI 君の自宅も JOI 君の通う大学も IOI 市内にある.IOI 市には N 個のバス停があり,1 から N までの番号が付いている.JOI 君の自宅の最寄りはバス停 1 で,大学の最 寄りはバス停 N である.
IOI 市内を走るバスは M 本あり,それぞれのバスは1日に1回,定められた時刻に定められたバス停を 出発し,定められた時刻に定められたバス停に到着する.日付をまたぐような運行を行うバスは存在しな い.JOI 君はバスに途中で乗ったりバスから途中で降りたりすることはできない.
JOI 君は毎日,1本以上のバスを乗り継いで大学に通っている.JOI 君がバスを乗り換えるのにかかる 時間は無視できるとする.すなわちある時刻にあるバス停を出発するバスに乗り換えるためには,そのバ スの出発時刻またはそれ以前にそのバス停に到着していればよい.また,同じバス停を複数回利用しても よい.
そのような条件のもとで,JOI 君はいつ家を出れば授業に間に合うように大学に到着できるかを知りた い.ただし大学は 1 日の初めの授業が開始する時刻が日によって異なる.ある Q 日間について,その日の 授業に間に合うためにはバス停 N にいつまでに到着すればよいかがわかっている.それぞれの日について, JOI 君は遅くともいつまでにバス停 1 に到着すれば授業に間に合うだろうか.
バスの運行に関する情報が与えられる.さらにある Q 日間について,バス停 N にいつまでに到着すれば よいかが与えられるので,それぞれについて,JOI 君が遅くともいつまでにバス停 1 に到着すればよいか を求めよ.
標準入力から以下の入力を読み込め.
標準出力に Q 行出力せよ.j 行目 (1 ≤ j ≤ Q) に,j 番目の日に JOI 君が遅くともいつまでにバス停 1 に 到着すればよいかを表す整数を出力せよ.ただし,授業に間に合うように大学に到着することが不可能な ときは -1 を出力せよ.
追加の制限はない.
5 6 1 2 10 25 1 2 12 30 2 5 26 50 1 5 5 20 1 4 30 40 4 5 50 70 4 10 30 60 100
-1 5 10 30
バス停 5 に時刻 10 までに到着することはできない.
時刻 30 までに到着するためには,時刻 5 に 4 番目のバスに乗ればよい.
時刻 60 までに到着するためには次のようにすればよい.
時刻 100 までに到着するためには次のようにすればよい.
3 8 1 2 1 5 1 3 0 1 1 3 2 8 2 3 2 3 2 3 3 4 2 3 4 5 2 3 5 6 2 3 6 7 6 3 4 5 6 7 8
0 0 0 1 1 2