AT_joi2026_yo2_d 買い物 3 (Shopping 3)

JOI 商店里有 $N$ 个商品，每个商品都编号为 $1$ 到 $N$。第 $i$ 个商品（$1 \leq i \leq N$）的定价为 $A_i$。 在 JOI 商店的网络购物中，购买商品时可以选择使用任意多张同种类型的优惠券（每种类型 $0$ 张及以上）。JOI 商店一共有 $Q$ 种优惠券，每种优惠券都编号为 $1$ 到 $Q$。 当你使用第 $j$ 种优惠券（$1 \leq j \leq Q$）$k$ 张时（$k \geq 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$ 个商品各一个时，所需支付的总金额最少是多少？ 给定商品及优惠券的信息，请编写程序计算并回答每个问题。

输入为如下格式： > $N$ $Q$ $A_1$ $A_2$ $\cdots$ $A_N$ $C_1$ $D_1$ > $C_2$ $D_2$ > $\vdots$ > $C_Q$ $D_Q$

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

### 小子任务 1. （$6$ 分）$N = 1$，$Q \leq 3\,000$。 2. （$3$ 分）$N \leq 100$，$Q \leq 100$，$A_i \leq 100$（$1 \leq i \leq N$）。 3. （$8$ 分）$N \leq 3\,000$，$Q \leq 3\,000$，$D_j = 1$（$1 \leq j \leq Q$）。 4. （$22$ 分）$N \leq 3\,000$，$Q \leq 3\,000$。 5. （$15$ 分）$D_j = 1$（$1 \leq j \leq Q$）。 6. （$18$ 分）$A_i \leq 1\,000\,000$（$1 \leq i \leq N$）。 7. （$28$ 分）无其他额外约束。 ### 样例解释 1 对于第 $1$ 个问题，使用 $1$ 张第 $1$ 种优惠券后各商品价格分别为 $3, 5, 0$，总价格为 $3 + 5 + 0 + 12 \times 1 = 20$。无法得到比 $20$ 更小的总价，所以输出 $20$。 对于第 $2$ 个问题，使用 $4$ 张第 $2$ 种优惠券后各商品价格分别为 $0, 2, 0$，总价格为 $0 + 2 + 0 + 3 \times 4 = 14$。无法得到比 $14$ 更小的总价，所以输出 $14$。 对于第 $3$ 个问题，使用 $2$ 张第 $3$ 种优惠券后各商品价格分别为 $0, 2, 0$，总价格为 $0 + 2 + 0 + 3 \times 2 = 8$。无法得到比 $8$ 更小的总价，所以输出 $8$。 对于第 $4$ 个问题，不使用第 $4$ 种优惠券，各商品价格分别为 $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 \leq N \leq 300\,000$。 - $1 \leq Q \leq 300\,000$。 - $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。 - $1 \leq C_j \leq 10^9$（$1 \leq j \leq Q$）。 - $1 \leq D_j \leq 10^9$（$1 \leq j \leq Q$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译