题目描述

某电话公司有 $N$ 种电话套餐。其中第 $i$ 个套餐，如果通话时间小于 $A_i$ 分钟则需要花费 $B_i$ 日元。超过该事件一分钟则超过每一分钟消费多一日元。

也就是说，如果通话时间为 $x(x\le A_i)$ 则花费为 $B_i+(x-A_i)$ 日元。

并且可以保证对于每个 $i$，通话时间为 $A_i$ 第 $i$ 个套餐比其余套餐更便宜。

给定 $M$ 个人。其中第 $i$ 个人的通话时间为 $T_i$。请对于每一个人，计算他的话费最小值。

数据范围

• $1\le N\le 10^5$
• $1\le M\le 10^5$
• $1\le A_i\le 10^9$
• $1\le B_i\le 10^9$
• $1\le T_i\le 10^9$
• 输入全部为整数

输入

输入全部按照以下格式。

N
A_1 B_1
...
A_N B_N
M
T_1
...
T_M

输出

对于每一个人，按顺序输出其话费最低值。

测试用例

测试用例 1

输入

2
5 6
3 5
2
4
8

输出

6
9

解说

• 第一个人无论选择套餐 $1$ 还是套餐 $2$，花费都是 $6$ 日元。
• 第二个人套餐 $1$ 花费 $9$ 日元，套餐 $2$ 花费 $10$ 日元，所以最低花费是 $9$ 日元。