Busy Beaver 在他的市场上卖蘑菇。每个蘑菇都有一个美味度指数，这是一个介于 $1$ 和 $N$（含）之间的整数。对于每个 $i$，有 $a_i$ 个美味度指数为 $i$ 的蘑菇。

Busy Beaver 只成对地卖蘑菇。每个蘑菇最多只能用于一个配对。一个配对可以通过以下方式之一出售：

• 类型 1：两个具有相同美味度指数的蘑菇，售价为 $x$。
• 类型 2：两个美味度指数恰好相差 1 的蘑菇（例如 $(3, 4)$），售价为 $y$。

给你 $Q$ 个场景。在第 $j$ 个场景中，价格为 $(x_j, y_j)$。对于每个场景，计算 Busy Beaver 可以获得的最大总利润。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含两个整数 $N$ 和 $Q$ ($2 \le N \le 3 \cdot 10^5$, $1 \le Q \le 3 \cdot 10^5$)。

每个测试用例的第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$ ($0 \le a_i \le 10^6$)。

接下来的 $Q$ 行中，每行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i \le 10^6$, $0 \le y_i \le 10^6$)，描述每个场景。

所有测试用例中 $N$ 的总和不超过 $3 \cdot 10^5$。

所有测试用例中 $Q$ 的总和不超过 $3 \cdot 10^5$。

输出格式

输出 $Q$ 行。

在第 $i$ 行中，输出 Busy Beaver 在第 $i$ 个场景中可以获得的最大利润。

子任务

本题共有五个子任务。

• （15 分）：$Q = 1$, $1 \le x_1 < y_1$
• （30 分）：对于每个 $i \in \{1, 2, \dots, Q\}$, $1 \le x_i < y_i$
• （15 分）：$Q = 1$, $1 \le y_1 < x_1$
• （30 分）：对于每个 $i \in \{1, 2, \dots, Q\}$, $1 \le y_i < x_i$
• （10 分）：无附加限制。

样例

输入样例 1

2
4 5
2 3 2 1
7 2
2 9
0 2
4 4
5 3
7 3
5 4 3 6 3 3 4
10 19
5 7
6 3

输出样例 1

21
36
8
16
16
247
92
75

说明

以下是第一个测试用例的解释。

在第一个场景中，最优方案是出售三个类型 1 的配对，如下所示：

$$(1, 1), (2, 2), (3, 3)$$

这可以获得 $21$ 的利润。

在第二个场景中，最优方案是出售四个类型 2 的配对，如下所示：

$$(1, 2), (1, 2), (2, 3), (3, 4)$$

这可以获得 $36$ 的利润。

在第五个场景中，最优方案是出售两个类型 1 的配对和两个类型 2 的配对，如下所示：

$$(1, 1), (2, 2), (2, 3), (3, 4)$$

这可以获得 $16$ 的利润。