Rocket Launching

Interview

Time limit2sMemory limit1024 MB

Summary

Given buildings at distances X_i with heights H_i, find for each query T the highest altitude Taro can be at by time T after climbing one ladder.

Level: Medium5 of 10
Topics: Sorting, Binary search, Array
Solved: No attempts yet

Problem

Taro is an ordinary beaver living in Beaverland. Beaverland measures time in byo (ビョウ).

Beaverland is flat, and the ground is at height 0 m everywhere. Beaverland has one rocket launch site and $N$ buildings, numbered 1 to $N$ . Building $i$ ( $1 \le i \le N$ ) stands perpendicular to the ground at a distance of $X_i$ m from Taro's house, and its height is $H_i$ m. Each building has a ladder that lets a person climb from the ground to the roof. Taro can walk on the ground at 1 m per byo and climb a ladder at 1 m per byo.

Tomorrow, a rocket carrying Beaverland's first Jupiter probe will launch from the launch site. Taro wants to watch the launch from as high a place as possible by climbing buildings with ladders.

Taro has no alarm clock, so he does not know when he will wake up tomorrow. He therefore makes plans for $Q$ cases. In plan $j$ ( $1 \le j \le Q$ ), Taro starts moving from his house exactly $T_j$ byo before the launch. For each plan, find the highest altitude he can reach at the moment of launch.

Input

The input is given in the following format.

N Q
X_1 H_1
X_2 H_2
\vdots
X_N H_N
T_1
T_2
\vdots
T_Q

Output

Print $Q$ lines. The $j$ -th line contains an integer, the highest altitude Taro can reach at the moment of launch in plan $j$ , where he starts moving from his house exactly $T_j$ byo before the launch.

Constraints

$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$ )
All input values are integers.

Examples4

Example 1
Input
```
4 3
3 2
4 4
1 2
2 3
2
1
10
```
Expected output
```
1
0
4
```
Example 2
Input
```
3 1
2 2
2 3
2 2
6
```
Expected output
```
3
```
Example 3
Input
```
3 4
2 2
4 3
5 4
6
3
9
7
```
Expected output
```
2
1
4
3
```

Example 4

Input

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

Expected output