第25回日本情報オリンピック　二次予選

2025年12月15日
情報オリンピック日本委員会

問題文

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

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

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

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

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

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

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

制約

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

小課題

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

入力

入力は以下の形式で与えられる．
N   Q
A₁   A₂   …   A_N
C₁   D₁
:
C_Q   D_Q

出力

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

入出力例

入力例 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 × 1 = 20 となる．20 より小さい合計金額を達成することはできないので，20 を出力する．

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

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

4 番目の質問において，種類 4 のクーポンを 0 枚使うことで各商品の価格は 8, 10, 3 となり，合計金額は 8 + 10 + 3 + 100 × 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 の制約を満たす．