配点: 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).
- 所有输入值都是整数。
小課題
- (6 点) N = 1,Q \leqq 3\,000.
- (3 点) N \leqq 100,Q \leqq 100,A_i \leqq 100 (1 \leqq i \leqq N).
- (8 点) N \leqq 3\,000,Q \leqq 3\,000,D_j = 1 (1 \leqq j \leqq Q).
- (22 点) N \leqq 3\,000,Q \leqq 3\,000.
- (15 点) D_j = 1 (1 \leqq j \leqq Q).
- (18 点) A_i \leqq 1\,000\,000 (1 \leqq i \leqq N).
- (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 满足约束。