Maximum Attractions

You are given a travel plan consisting of cities with a number of attractions. For each test case, you are given an array A of length \(N\) where each element represents the number of attractions in a city. In addition, you are provided \(M\) segments, each represented by two integers \(L\) and \(R\). For each segment, the sum of attractions is given by:

\(S = \sum_{i=L}^{R} A_i\)

Your task is to determine the maximum possible attractions sum among all given segments for each test case.

Input Format: The input is given from stdin and consists of multiple test cases. The first line contains a single integer \(T\), denoting the number of test cases. For each test case, the first line contains two integers \(N\) and \(M\) denoting the number of cities and segments, respectively. The next line contains \(N\) space-separated integers representing the attractions in each city. This is followed by \(M\) lines, each containing two integers \(L\) and \(R\) that define a segment.

Output Format: For each test case, output a single line with the maximum attractions sum found among the segments.

inputFormat

The input is read from stdin and follows the format below:

T
N M
A[1] A[2] ... A[N]
L1 R1
L2 R2
... 
LM RM
... (repeat for T test cases)

</p>

outputFormat

For each test case, output the maximum attractions sum obtainable by selecting one segment. Each answer should be printed on a separate line to stdout.

## sample

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

10

</p>