Problem B
Monsters, Inc

The brave knight Okyt is standing before a line of monsters. There are $N$ monsters arranged in a row, and he must face them in order, starting from the first and moving to the last. Each monster has a strength requirement — to defeat the $i$-th monster, Okyt’s current strength must be at least $s_i$. If he defeats it, his strength increases by $b_i$.

You are given $Q$ queries. Each query gives you a starting strength, and your task is to determine how many monsters Okyt can defeat in order before his strength becomes insufficient.

Input

The first line contains a single integer $1 \le N \le 10^5$, the number of monsters.

The next $N$ lines each contain two integers $0 \le s_i, b_i \le 10^9$, where $s_i$ is the strength required to beat the $i$-th monster and $b_i$ is the strength Okyt gains after defeating it.

The next line contains a single integer $1 \le Q \le 10^5$, the number of queries.

Each of the following $Q$ lines contains a single integer $0 \le x \le 10^9$, Okyt’s starting strength for that query. NOTE: The queries are given in ascending order of $x$.

Output

For each query, output a single integer — the number of monsters you can defeat with the given starting strength.

Scoring

3
2 1
3 0
4 5
4
1
2
3
4

0
2
3
3

5
3 2
5 1
4 3
10 10
15 5
3
2
3
9

0
3
5