配点 : 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