Problem Description

A certain telephone company has $N$ types of calling plans.

If plan $i$ is chosen, the monthly charge is $B_i$ yen for up to $A_i$ minutes of talk time, and for any additional talk time, an extra charge of 1 yen per minute is incurred.

For example, if the talk time is $x$ minutes ($x \geq A_i$), the charge for plan $i$ is $B_i + (x - A_i)$ yen.

For all plans $i$, it is guaranteed that if the talk time is $A_i$ minutes, the charge for plan $i$ is at least 1 yen cheaper than any other plan.

There are $M$ people, and person $i$ has a monthly talk time of $T_i$ minutes.

For each person, find the minimum possible charge for their talk time.

Input Format

The input is given from the standard input in the following format:

$N$ $A_1$ $B_1$ $:$ $A_N$ $B_N$ $M$ $T_1$ $:$ $T_M$

Output Format

For each person, output the minimum possible charge for their talk time in order.

Sample Input and Output

Sample Input #1

2
5 6
3 5
2
4
8

Sample Output #1

6
9

Sample Input #2

4
12 5
1 1
7 3
243 32
6
632
188
69
54
14
36

Sample Output #2

421
32
32
32
7
29

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• $1 \leq T_i \leq 10^9$
• All inputs are integers
• It is guaranteed that if the talk time is $A_i$ minutes, the charge for plan $i$ is at least 1 yen cheaper than any other plan.

Sample Explanation 1

• If person $1$ chooses plan $1$, the charge is $6$ yen.
• If person $1$ chooses plan $2$, the charge is $6$ yen.
  Therefore, the minimum charge for person $1$ is $6$ yen.
• If person $2$ chooses plan $1$, the charge is $9$ yen.
• If person $2$ chooses plan $2$, the charge is $10$ yen.
  Therefore, the minimum charge for person $2$ is $9$ yen.

见题面 Input 部分

见题面 Output 部分