区间求和

题目描述

给定序列 $a_{1\sim n}$ 与 $q$ 次询问，每次询问给出 $l, r$，求 $a_{l\sim r}$ 的和。可以在询问前任意交换元素位置，求所有询问答案之和的最大值。

输入格式

第一行 $T$。每组：第一行 $n, q$；第二行 $n$ 个整数 $a_{1\sim n}$；接下来 $q$ 行每行 $l_i, r_i$。

输出格式

每组输出一行最大询问答案之和。

数据范围

$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$

样例

样例输入

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

样例输出

23
4