AT_code_festival_2018_final_c Telephone Charge

[problemUrl]: https://atcoder.jp/contests/code-festival-2018-final/tasks/code_festival_2018_final_c ある電話会社では、通話料金のプランが $ N $ 種類あります。 プラン $ i $ を選んだ場合、ひと月あたり $ A_i $ 分以内の通話時間ならば $ B_i $ 円、それ以上の通話時間の場合は 超過時間 $ 1 $ 分あたり $ 1 $ 円の通話料金がかかります。 例えば、通話時間が $ x(x\geq\ A_i) $ 分の場合のプラン $ i $ での通話料金は $ B_i+(x-A_i) $ 円です。 また、全てのプラン $ i $ に対して、通話時間が $ A_i $ 分の場合には他のどのプランよりも通話料金が $ 1 $ 円以上安くなることが保証されます。 人が $ M $ 人いて、人 $ i $ のひと月あたりの通話時間は $ T_i $ 分です。 全ての人に対して、とりうる通話料金の最安値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ : $ $ A_N $ $ B_N $ $ M $ $ T_1 $ $ : $ $ T_M $

全ての人に対し、とりうる通話料金の最安値を、順に出力せよ。

### 制約 - $ 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 $ 円以上安くなることが保証される ### Sample Explanation 1 \- 人 $ 1 $ がプラン $ 1 $ を選んだ場合の通話料金は $ 6 $ 円です。 - 人 $ 1 $ がプラン $ 2 $ を選んだ場合の通話料金は $ 6 $ 円です。 よって、人 $ 1 $ の通話料金の最安値は $ 6 $ 円です。 - 人 $ 2 $ がプラン $ 1 $ を選んだ場合の通話料金は $ 9 $ 円です。 - 人 $ 2 $ がプラン $ 2 $ を選んだ場合の通話料金は $ 10 $ 円です。 よって、人 $ 2 $ の通話料金の最安値は $ 9 $ 円です。