题目描述

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

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

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

输入格式

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

第一行两个整数 n,q。

第二行 n 个整数 $a_{1∼n}$。

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

输出格式

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

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

23
4

数据范围

对于 30% 的数据，1≤T≤10，1≤n,q≤10。

对于 60% 的数据，1≤T≤10，1≤n,q≤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$。

提示

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