Calculate Decorated Subway Line Length

Given a subway system with (N) stations located along a one-dimensional coordinate line and (M) decoration plans, your task is to calculate the total length of the subway line that gets decorated. Each decoration plan is specified by two 1-indexed integers (s_i) and (e_i) indicating the starting and ending station indices. The corresponding decorated segment extends from coordinate (a_{s_i}) to (a_{e_i}), where (a_1, a_2, \ldots, a_N) are the coordinates of the stations. Note that decoration plans can overlap. In such cases, overlapping segments should be merged, and the total decorated length is the sum of the lengths of these merged segments.

For example, if a plan decorates from station 1 to station 3 and another from station 2 to station 4, the decorated segment spans from station 1's coordinate to station 4's coordinate.

inputFormat

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

N M
a1 a2 ... aN
s1 e1
s2 e2
...
sM eM

Here, the first line contains two integers (N) and (M) representing the number of stations and the number of decoration plans, respectively. The second line contains (N) integers, the coordinates of each station. The next (M) lines each contain two integers (s_i) and (e_i), giving the starting and ending station indices for the decoration plan.

outputFormat

Output a single integer to standard output (stdout), which is the total length of the subway line that is decorated after merging all overlapping decoration segments.## sample

5 3
1 3 6 10 15
1 3
2 4
3 5

14