← 返回题目列表

AtCoder · code_festival_2018_final_c

C. 电话费

中文机器翻译题面 查看原题

配点 : 300 点

問題文

在某电话公司,有通话费用的套餐 N 种类。

普兰 i 如果选择了该套餐,每月 A_i 分钟以内的通话时间的话 B_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