28021번 - Rocket Launching 서브태스크다국어

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

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

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

しかし，ビ太郎は目覚まし時計を持っていないため，明日いつ起きられるか分からない．そのため，$Q$ 個 の場合について計画を立てることにした．$j$ 個目 ($1 ≦ j ≦ 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 ≦ j ≦ Q$) には，ロケット打ち上げのちょうど $T_j$ ビョウ前にビ太郎 がビ太郎の家から移動を開始した場合に，ロケット打ち上げの瞬間に最大で標高何 m の地点に辿り着ける かを表す整数を出力せよ．

• $1 ≦ N ≦ 300\,000$．
• $1 ≦ Q ≦ 300\,000$．
• $1 ≦ X_i ≦ 10^9$ ($1 ≦ i ≦ N$)．
• $1 ≦ H_i ≦ 10^9$ ($1 ≦ i ≦ N$)．
• $1 ≦ T_j ≦ 10^9$ ($1 ≦ j ≦ Q$)．
• 入力される値はすべて整数である．