You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

$Alice$ 最近正在学习前缀和：给定序列 $a_1 \sim a_n$ 与 $q$ 次询问，每次询问给出 $l, r$，求 $a_l \sim a_r$的和。这样的问题对 $Alice$ 来说已经太简单了，他发现交换一些序列 $a$ 中的元素的值可以改变询问的结果。

面对这个发现，他提出了一个新的问题：给定序列 $a_1 \sim a_n$与 $q$ 次询问，每次询问给出 $l, r$，如果可以在执行询问前任意次交换 $a$ 中两个元素的位置得到 $a_1\sim a_n$′，所有询问的答案之和最大是多少？一次询问的答案指的是 $a_l \sim a_r$的和。

需要注意的是，$Alice$ 只能在开始询问前交换元素，然后求出所有询问的答案之和。

Format

Input

第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $a_1 \sim a_n$。

接下来 $q$ 行，第 $i$ 行两个整数 $l_i, r_i$ 表示第 $i$ 次询问的参数。

Output

对于每组数据，输出一行一个答案表示最大的询问答案之和。

Samples

样例输入

2
5 2
1 2 3 4 5
1 4
2 3
2 3
1 1
1 1
1 2
2 2

样例输出

23
4

样例解释

样例解释：对于第一组数据，把a变为2 4 5 3 1即可得到答案之和为23，可以验证没有更大的答案之和。

Limitation

对于$30\%$ 的数据，$1 \leq T \leq 10, 1 \leq n, q \leq 10$

对于 $60\%$ 的数据，$1 \leq T \leq 10, 1 \leq n, q \leq 1000$

对于 $100\%$ 的数据，$1 \leq T \leq 10^4, 1 \leq n, \sum{n} \leq 2 \times 10^5, 1 \leq q, \sum{q} \leq 2 \times 10^5, 1 \leq a_i \leq 10^5, 1 \leq l \leq r \leq n$