问题文

某个电话公司有 $N$ 种通话费套餐。

选择套餐 $i$，如果每月通话时间不超过 $A_i$ 分钟，则费用为 $B_i$ 元；如果超过 $A_i$ 分钟，则每超出 $1$ 分钟需要支付 $1$ 元的超时通话费用。

例如，对于通话时间为 $x(x ≥ A_i)$ 分钟的情况下选择套餐 $i$，通话费用为 $B_i+(x-A_i)$ 元。

此外，对于所有套餐 $i$，保证当通话时间为 $A_i$ 分钟时，该套餐的通话费用会比其他套餐便宜至少 1 元。

现在有 $M$ 个人，第 $i$ 个人每月的通话时间是 $T_i$ 分钟。

请计算每个人可能的最低通话费用。

约束条件

• $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$
• 输入均为整数
• 保证当通话时间为 $A_i$ 分钟时，套餐 $i$ 的通话费用会比其他套餐便宜至少 1 元

输入

从标准输入读取输入数据，输入格式如下：

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

输出

按顺序输出每个人的可能的最低通话费用。

示例输入1

2
5 6
3 5
2
4
8

示例输出1

6
9

• 人员1选择方案1时的通话费用为6元。

• 人员1选择方案2时的通话费用为6元。因此，人员1的最低通话费用为6元。

• 人员2选择方案1时的通话费用为9元。

• 人员2选择方案2时的通话费用为10元。因此，人员2的最低通话费用为9元。

示例输入2

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

示例输出2

421
32
32
32
7
29