問題文

ある電話会社では、通話料金のプランが 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 円以上安くなることが保証される

入力例 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