問題文

ある電話会社では、通話料金のプランが $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