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$ )．
入力される値はすべて整数である．