問題文

JOI 商店には N 個の商品があり，商品には 1 から N までの番号が付けられている．商品 i (1 \leqq i \leqq N) の定価は A_i である．

JOI 商店のインターネット通販では，商品を購入するときに単一の種類のクーポンを 0 枚以上の好きな枚数だけ使用することができる．JOI 商店のクーポンは Q 種類存在し，クーポンの種類には 1 から Q までの番号が付けられている．

種類 j (1 \leqq j \leqq Q) のクーポンを k 枚 (k \geqq 0) 使用したときの効果は以下の通りである．

• i = 1, 2, \dots, N について，商品 i の価格が \max(0,\ A_i - D_j \times k) になる(ここで，\max(0,\ A_i - D_j \times k) は 0 と A_i - D_j \times k のうち小さくないほうを表す)．
• 商品の価格とは別に，C_j \times k の追加料金がかかる．

各クーポンの種類に対応して，Q 個の質問が考えられる．j 番目の質問は以下の通りである．

• 種類 j のクーポンのみを使用して N 個の商品を 1 つずつ買う場合，払う合計金額の最小値は何か．

商品とクーポンの情報が与えられたとき，各質問への答えを求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 300\,000．
• 1 \leqq Q \leqq 300\,000．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• 1 \leqq C_j \leqq 10^9 (1 \leqq j \leqq Q)．
• 1 \leqq D_j \leqq 10^9 (1 \leqq j \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (6 点) N = 1，Q \leqq 3\,000．
2. (3 点) N \leqq 100，Q \leqq 100，A_i \leqq 100 (1 \leqq i \leqq N)．
3. (8 点) N \leqq 3\,000，Q \leqq 3\,000，D_j = 1 (1 \leqq j \leqq Q)．
4. (22 点) N \leqq 3\,000，Q \leqq 3\,000．
5. (15 点) D_j = 1 (1 \leqq j \leqq Q)．
6. (18 点) A_i \leqq 1\,000\,000 (1 \leqq i \leqq N)．
7. (28 点) 追加の制約はない．

入力例 1

3 4
8 10 3
12 5
3 2
3 4
100 100

出力例 1

20
14
8
21

1 番目の質問において，種類 1 のクーポンを 1 枚使うことで各商品の価格は 3, 5, 0 となり，合計金額は 3 + 5 + 0 + 12 \times 1 = 20 となる．20 より小さい合計金額を達成することはできないので，20 を出力する．

2 番目の質問において，種類 2 のクーポンを 4 枚使うことで各商品の価格は 0, 2, 0 となり，合計金額は 0 + 2 + 0 + 3 \times 4 = 14 となる．14 より小さい合計金額を達成することはできないので，14 を出力する．

3 番目の質問において，種類 3 のクーポンを 2 枚使うことで各商品の価格は 0, 2, 0 となり，合計金額は 0 + 2 + 0 + 3 \times 2 = 8 となる．8 より小さい合計金額を達成することはできないので，8 を出力する．

4 番目の質問において，種類 4 のクーポンを 0 枚使うことで各商品の価格は 8, 10, 3 となり，合計金額は 8 + 10 + 3 + 100 \times 0 = 21 となる．21 より小さい合計金額を達成することはできないので，21 を出力する．

この入力例は小課題 2, 4, 6, 7 の制約を満たす．

入力例 2

1 3
83
2 5
4 5
6 5

出力例 2

34
67
83

この入力例は小課題 1, 2, 4, 6, 7 の制約を満たす．

入力例 3

15 3
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
1 1
10 1
20 1

出力例 3

9
67
77

この入力例は小課題 2, 3, 4, 5, 6, 7 の制約を満たす．

入力例 4

6 3
1000000000 999999999 999999998 999999997 999999996 999999995
1000000000 1
1 1000000000
900000000 900000000

出力例 4

5999999985
1
1499999985

この入力例は小課題 4, 7 の制約を満たす．