D. Sell in Pairs
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Busy Beaver sells mushrooms at his market. Each mushroom has a flavor index, an integer between $$$1$$$ and $$$N$$$ (inclusive). For each $$$i$$$, there are $$$a_i$$$ mushrooms of flavor index $$$i$$$.

Busy Beaver sells mushrooms only in pairs. Each mushroom can be used in at most one pair. A pair can be sold in one of the following ways:

  • Type 1: two mushrooms with the same flavor index for price $$$x$$$.
  • Type 2: two mushrooms whose flavor indices differ by exactly $$$1$$$ (e.g. $$$(3,4)$$$) for price $$$y$$$.

You are given $$$Q$$$ scenarios. In the $$$j$$$-th scenario, the prices are $$$(x_j, y_j)$$$. For each scenario, compute the maximum total profit Busy Beaver can obtain.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 3 \cdot 10^5$$$, $$$1 \le Q \le 3 \cdot 10^5$$$).

The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$0 \le a_i \le 10^6$$$).

Each of the next $$$Q$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i \le 10^6$$$, $$$0 \le y_i \le 10^6$$$), describing each scenario.

The sum of $$$N$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

The sum of $$$Q$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

Print $$$Q$$$ lines.

On the $$$i$$$-th line, output the maximum profit Busy Beaver can obtain in the $$$i$$$-th scenario.

Scoring

There are five subtasks for this problem.

  • ($$$15$$$ points): $$$Q = 1$$$, $$$1 \le x_1 \lt y_1$$$
  • ($$$30$$$ points): For each $$$i \in \{1, 2, \dots, Q\}$$$, $$$1 \le x_i \lt y_i$$$
  • ($$$15$$$ points): $$$Q = 1$$$, $$$1 \le y_1 \lt x_1$$$
  • ($$$30$$$ points): For each $$$i \in \{1, 2, \dots, Q\}$$$, $$$1 \le y_i \lt x_i$$$
  • ($$$10$$$ points): No additional constraints.
Example
Input
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
Output
21
36
8
16
16
247
92
75
Note

Below is the explanation for the first test case.

In the first scenario, it is optimal to sell three type 1 pairs as follows: $$$$$$ (1, 1), (2, 2), (3, 3) $$$$$$ which yields a profit of $$$21$$$.

In the second scenario, it is optimal to sell four type 2 pairs as follows: $$$$$$ (1, 2), (1, 2), (2, 3), (3, 4) $$$$$$ which yields a profit of $$$36$$$.

In the fifth scenario, it is optimal to sell two type 1 pairs and two type 2 pairs as follows: $$$$$$ (1, 1), (2, 2), (2, 3), (3, 4) $$$$$$ which yields a profit of $$$16$$$.