AT_joi2026_yo2_d 買い物 3 (Shopping 3)

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 $ つずつ買う場合，払う合計金額の最小値は何か． 商品とクーポンの情報が与えられたとき，各質問への答えを求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ C_1 $ $ D_1 $ $ \vdots $ $ C_Q $ $ D_Q $

$ Q $ 行出力せよ． $ j $ 行目 ( $ 1 \leqq j \leqq Q $ ) には， $ j $ 番目の質問への答えを出力せよ．

### 小課題 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 $ 点) 追加の制約はない． ### Sample Explanation 1 $ 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 $ の制約を満たす． ### Sample Explanation 2 この入力例は小課題 $ 1, 2, 4, 6, 7 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 2, 3, 4, 5, 6, 7 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 4, 7 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．