Skip to content
Sign in

買い物 3 (Shopping 3)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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\) つずつ買う場合，払う合計金額の最小値は何か．

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

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\))．
  • 入力される値はすべて整数である．

Subtasks

  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\) 点) 追加の制約はない．

Input

入力は以下の形式で与えられる．

\(N\) \(Q\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(C_1\) \(D_1\)
\(\vdots\)
\(C_Q\) \(D_Q\)

Output

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

Examples

Sample input 1
3 4
8 10 3
12 5
3 2
3 4
100 100
Sample output 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\) の制約を満たす．

Sample input 2
1 3
83
2 5
4 5
6 5
Sample output 2
34
67
83

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

Sample input 3
15 3
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
1 1
10 1
20 1
Sample output 3
9
67
77

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

Sample input 4
6 3
1000000000 999999999 999999998 999999997 999999996 999999995
1000000000 1
1 1000000000
900000000 900000000
Sample output 4
5999999985
1
1499999985

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

Notes

JOI 2026 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source