로켓 발사

면접 대비

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

요약

각 건물은 집에서 X_i m 떨어져 있고 높이는 H_i m입니다. 각 질의 T마다 출발 후 T 시간에 도달할 수 있는 가장 높은 고도를 구합니다.

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

문제

비타로는 비버랜드에 사는 평범한 비버이다. 비버랜드에서는 시간 단위로 뵤(ビョウ)를 쓴다.

비버랜드는 평평한 땅이라서 어디서든 지면의 표고가 $0$ m이다. 비버랜드에는 로켓 발사 기지가 하나 있고, 빌딩이 $N$ 채 있다. 빌딩에는 $1$ 부터 $N$ 까지 번호가 붙어 있다. 빌딩 $i$ ( $1 \le i \le N$ )는 비타로의 집에서 $X_i$ m 떨어진 곳에 지면과 수직으로 서 있고, 높이는 $H_i$ m이다. 각 빌딩에는 사다리가 있어서, 사다리를 이용하면 지면에서 옥상까지 올라갈 수 있다. 비타로는 지면을 1뵤에 1 m씩 걸을 수 있고, 사다리로 빌딩을 1뵤에 1 m씩 오를 수 있다.

내일 로켓 발사 기지에서 목성 탐사선을 실은 로켓이 발사된다. 비타로는 사다리로 빌딩을 올라 가능한 한 높은 곳에서 발사를 보려고 한다.

비타로는 알람 시계가 없어서 내일 몇 시에 일어날지 알 수 없다. 그래서 $Q$ 가지 경우에 대해 계획을 세우기로 했다. $j$ 번째 ( $1 \le j \le Q$ ) 계획에서는 로켓 발사 정확히 $T_j$ 뵤 전에 비타로가 집에서 이동을 시작한다. 각 계획마다 발사 순간에 도달할 수 있는 최대 표고를 구하라.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.

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 \le j \le Q$ )에는 로켓 발사 정확히 $T_j$ 뵤 전에 비타로가 집에서 이동을 시작했을 때, 발사 순간에 도달할 수 있는 최대 표고를 나타내는 정수를 출력하라.

제한

$1 \le N \le 300\,000$
$1 \le Q \le 300\,000$
$1 \le X_i \le 10^9$ ( $1 \le i \le N$ )
$1 \le H_i \le 10^9$ ( $1 \le i \le N$ )
$1 \le T_j \le 10^9$ ( $1 \le j \le 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

예상 출력