C - Telephone Charge

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