A - ロケット打ち上げ (Rocket Launching) 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

ビーバーのビ太郎はビーバーランドに住むごく普通のビーバーである.ビーバーランドでは,時間の単位としてビョウを用いている.

ビーバーランドは平らな土地であり,地面の標高はどこでも 0\:\textrm{m} である.ビーバーランドには,ロケット発射基地が 1 つとビルが N 棟あり,ビルには 1 から N までの番号が付けられている.ビル i (1 \leqq i \leqq N) はビ太郎の家から X_{i}\:\textrm{m} 離れた地点に地面と垂直に建っており,高さは H_{i}\:\textrm{m} である.各ビルには,はしごがついていて,はしごを使うことで地面から屋上まで上ることができる.ビ太郎は地面を毎ビョウ 1\:\textrm{m} の速さで移動でき,はしごを使って毎ビョウ 1\:\textrm{m} の速さでビルを上ることができる.

明日,ビーバーランド初の木星探査機を載せたロケットがロケット発射基地から打ち上げられる.これを知ったビ太郎は,はしごを使ってビルを上ることで,できる限り高い所で打ち上げを見ることにした.

しかし,ビ太郎は目覚まし時計を持っていないため,明日いつ起きられるか分からない.そのため,Q 個の場合について計画を立てることにした.j 個目 (1 \leqq j \leqq Q) の計画では,ロケット打ち上げのちょうど T_{j} ビョウ前にビ太郎がビ太郎の家から移動を開始した場合に,ロケット打ち上げの瞬間に最大で標高何 m の地点に辿り着けるかを求めたい.

ビルとビ太郎の計画の情報が与えられるので,各計画についてロケット打ち上げの瞬間にビ太郎が最大で標高何 m の地点に辿り着けるかを求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.

N Q
X_{1} H_{1}
X_{2} H_{2}
\vdots
X_{N} H_{N}
T_{1}
T_{2}
\vdots
T_{Q}

出力

標準出力に Q 行出力せよ.j 行目 (1 \leqq j \leqq Q) には,ロケット打ち上げのちょうど T_{j} ビョウ前にビ太郎がビ太郎の家から移動を開始した場合に,ロケット打ち上げの瞬間に最大で標高何 m の地点に辿り着けるかを表す整数を出力せよ.

制約

  • 1 \leqq N \leqq 300\,000.
  • 1 \leqq Q \leqq 300\,000.
  • 1 \leqq X_{i} \leqq 10^{9} (1 \leqq i \leqq N).
  • 1 \leqq H_{i} \leqq 10^{9} (1 \leqq i \leqq N).
  • 1 \leqq T_{j} \leqq 10^{9} (1 \leqq j \leqq Q).
  • 入力される値はすべて整数である.

小課題

  1. (10 点) N \leqq 1\,000,Q \leqq 1\,000.
  2. (15 点) X_{i} \leqq 30 (1 \leqq i \leqq N).
  3. (16 点) H_{i} \leqq 30 (1 \leqq i \leqq N).
  4. (29 点) X_{i} < X_{i+1},H_{i} < H_{i+1} (1 \leqq i \leqq N - 1).
  5. (30 点) 追加の制約はない.

入力例 1

4 3
3 2
4 4
1 2
2 3
2
1
10

出力例 1

1
0
4

1 個目の計画では,ビ太郎は以下のように移動すると,ロケット打ち上げの瞬間に標高 1\:\textrm{m} の地点に辿り着くことができる.

  1. 1 ビョウかけて地面をビル 3 まで移動する.
  2. 1 ビョウかけてはしごを使ってビル 3 を 1\:\textrm{m} 上る.

ロケット打ち上げの瞬間に 1\:\textrm{m} より標高が高い位置にいることはできないので,1 行目には 1 を出力する.

2 個目の計画では,どのように移動してもビ太郎はロケット打ち上げの瞬間に標高 0\:\textrm{m} の地点にいることになる.よって,2 行目には 0 を出力する.

3 個目の計画では,ビ太郎は 4 ビョウかけてビル 2 まで移動し,はしごを使うことでビル 2 を 4 ビョウ間上ってビル 2 の屋上に行き,更にそこで 2 ビョウ待つと,ロケット打ち上げの瞬間に標高 4\:\textrm{m} の地点にいることができる.ロケット打ち上げの瞬間に 4\:\textrm{m} より標高が高い位置にいることはできないので,3 行目には 4 を出力する.

この入力例は小課題 1, 2, 3, 5 の制約を満たす.

入力例 2

3 1
2 2
2 3
2 2
6

出力例 2

3

この入力例は小課題 1, 2, 3, 5 の制約を満たす.

入力例 3

3 4
2 2
4 3
5 4
6
3
9
7

出力例 3

2
1
4
3

この入力例はすべての小課題の制約を満たす.

入力例 4

6 8
254859174 143139414
93613293 194935142
357382831 801995983
975916146 20247892
739377425 753031505
735561543 682006760
595240078
728158226
31923474
128550227
52197244
332004808
814747290
951530008

出力例 4

237857247
370775395
0
34936934
0
194935142
457364459
594147177

この入力例は小課題 1, 5 の制約を満たす.


出典

JOIG 2022/2023 春季トレーニング Contest Day1 問題1