AT_code_festival_2018_final_c Telephone Charge

某电话公司有 $N$ 种通话资费套餐。 选择第 $i$ 种套餐时，如果每月通话时间不超过 $A_i$ 分钟，则通话费用为 $B_i$ 日元；如果超过 $A_i$ 分钟，则超出部分每分钟需额外支付 $1$ 日元。 例如，若通话时间为 $x(x\geq A_i)$ 分钟，选择第 $i$ 种套餐时的通话费用为 $B_i+(x-A_i)$ 日元。 此外，保证对于所有套餐 $i$，当通话时间为 $A_i$ 分钟时，套餐 $i$ 的通话费用比其他任意套餐都至少便宜 $1$ 日元。 现有 $M$ 个人，第 $i$ 个人每月通话时间为 $T_i$ 分钟。 请为每个人求出可能的最低通话费用。

输入以如下格式从标准输入读入。 > $N$ $A_1$ $B_1$ $:$ $A_N$ $B_N$ $M$ $T_1$ $:$ $T_M$

请依次输出每个人可能的最低通话费用。

## 限制条件 - $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$ 日元 ## 样例解释 1 - 人 $1$ 选择套餐 $1$ 时的通话费用为 $6$ 日元。 - 人 $1$ 选择套餐 $2$ 时的通话费用为 $6$ 日元。 因此，人 $1$ 的最低通话费用为 $6$ 日元。 - 人 $2$ 选择套餐 $1$ 时的通话费用为 $9$ 日元。 - 人 $2$ 选择套餐 $2$ 时的通话费用为 $10$ 日元。 因此，人 $2$ 的最低通话费用为 $9$ 日元。 由 ChatGPT 4.1 翻译