Rocket Launching

시간 제한2초메모리 제한1024 MB

요약

위치 X_i에 높이 H_i인 빌드 N개가 있을 때, 각 질의 T에 대해 비타로가 1 m/s로 걷고 사다리로 1 m/s로 오르며 T초 동안 도달할 수 있는 최대 높이를 구한다. reach at most reachable. He starts at the origin. For a given time T, if he reaches building i, the time cost is X_i (walking) plus some climb. The total time budget is T. He wants to maximize the altitude reached at time exactly T. If T >= X_i + H_i, he can reach height H_i (or higher if a further building). The maximum height at time T is the answer. This is equivalent to: answer(T) = max over i with X_i <= T of min(H_i, T - X_i)? No wait: he can arrive at building i at time X_i, then climb forT

난이도: 보통10점 중 7점
유형: 정렬, 이분 탐색, 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

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

ビーバーランドは平らな土地であり，地面の標高はどこでも $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$ )．
入力される値はすべて整数である．

예제4

예제 1
입력
```
4 3
3 2
4 4
1 2
2 3
2
1
10
```
예상 출력
```
1
0
4
```
예제 2
입력
```
3 1
2 2
2 3
2 2
6
```
예상 출력
```
3
```
예제 3
입력
```
3 4
2 2
4 3
5 4
6
3
9
7
```
예상 출력
```
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

예상 출력