C - Telephone Charge
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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