← 返回题目列表

AtCoder · joi2026_yo2_d

D. 购物3

中文机器翻译题面 查看原题

配点: 100 点

問題文

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 点)没有额外的限制。

入力

输入按以下格式给出。

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

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 满足约束。