题目描述

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$ 个问题的答案。

3 4
8 10 3
12 5
3 2
3 4
100 100

20
14
8
21

1 3 
83
2 5
4 5
6 5

34
67
83

15 3
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
1 1
10 1
20 1

9
67
77

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

5999999985
1
1499999985

提示

样例解释

样例 $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$ 分）无额外约束。