P14798 [JOI 2026 二次预选] 购物 3 / Shopping 3

JOI 商店里有 $N$ 个商品，商品被编号为 $1$ 到 $N$。商品 $i$（$1 \le i \le N$）的标价是 $A_i$。 在 JOI 商店的网络购物中，购买商品时可以选择使用同一种类的优惠券 $0$ 张以上，并且可以使用任意张数。JOI 商店一共有 $Q$ 种优惠券，优惠券种类编号为 $1$ 到 $Q$。 当使用种类 $j$（$1 \le j \le Q$）的优惠券 $k$ 张（$k \ge 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\ \ \dots\ \ A_N$ > $C_1\ \ D_1$ > $\vdots$ > $C_Q\ \ D_Q$

输出 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）输出第 $j$ 个问题的答案。

### 样例解释 #### 样例 $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$ 的约束。 #### 样例 $2$ 解释 该输入示例满足子任务 $1, 2, 4, 6, 7$ 的约束。 #### 样例 $3$ 解释 该输入示例满足子任务 $2, 3, 4, 5, 6, 7$ 的约束。 #### 样例 $4$ 解释 该输入示例满足子任务 $4, 7$ 的约束。 ### 约束 - $1 \le N \le 300\,000$。 - $1 \le Q \le 300\,000$。 - $1 \le A_i \le 10^9$（$1 \le i \le N$）。 - $1 \le C_j \le 10^9$（$1 \le j \le Q$）。 - $1 \le D_j \le 10^9$（$1 \le j \le Q$）。 - 输入值均为整数。 ### 子任务 - （$6$ 分）$N = 1$，$Q \le 3\,000$。 - （$3$ 分）$N \le 100$，$Q \le 100$，$A_i \le 100$（$1 \le i \le N$）。 - （$8$ 分）$N \le 3\,000$，$Q \le 3\,000$，$D_j = 1$（$1 \le j \le Q$）。 - （$22$ 分）$N \le 3\,000$，$Q \le 3\,000$。 - （$15$ 分）$D_j = 1$（$1 \le j \le Q$）。 - （$18$ 分）$A_i \le 1\,000\,000$（$1 \le i \le N$）。 - （$28$ 分）无额外约束。