AT_joi2026_yo2_d.買い物 3 (Shopping 3)

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

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$ 个问题如下：

给定商品及优惠券的信息，请编写程序计算并回答每个问题。

输入为如下格式：

$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

输出#1

输入#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

输入#4

6 3
1000000000 999999999 999999998 999999997 999999996 999999995
1000000000 1
1 1000000000
900000000 900000000

输出#4

5999999985
1
1499999985

对于第 $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$ 的约束。

该输入示例满足小子任务 $1, 2, 4, 6, 7$ 的约束。

该输入示例满足小子任务 $2, 3, 4, 5, 6, 7$ 的约束。

该输入示例满足小子任务 $4, 7$ 的约束。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?