The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of $n$ elements (the elements of the array are indexed starting from 1); also, there are $q$ queries, each one is defined by a pair of integers $l_i$, $r_i$ $(1 \le l_i \le r_i \le n)$. You need to find for each query the sum of elements of the array with indexes from $l_i$ to $r_i$, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.
The first line contains two space-separated integers $n$ ($1 \le n \le 2\cdot10^5$) and $q$ ($1 \le q \le 2\cdot10^5$) — the number of elements in the array and the number of queries, correspondingly.

The next line contains $n$ space-separated integers $a_i$ ($1 \le a_i \le 2\cdot10^5$) — the array elements.

Each of the following $q$ lines contains two space-separated integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the $i$-th query.
a, b = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
d = {}
queries = []
for idx in range(b):
    left, right = map(int, input().split())
    for k in range(left, right + 1):
        if k in d:
            d[k] += 1
        else:
            d[k] = 1
    queries.append([left, right])
arr = []
for key, val in d.items():
    arr.append([key, val])
# array = [1, 2, 3, 4, 5]
# arr = [[1, 1], [2, 3], [3, 3], [4, 1], [5, 1]]
# queries = [[1, 5], [2, 3], [2, 3]]
for it1 in range(len(arr) - 1):
    for it2 in range(it1 + 1, len(arr)):
        if arr[it1][1] > arr[it2][1]:
            arr[it2][0], arr[it1][0] = arr[it1][0], arr[it2][0]
            arr[it2][1], arr[it1][1] = arr[it1][1], arr[it2][1]
        if arr[it1][1] == arr[it2][1]:
            if arr[it1][0] < arr[it2][0]:
                arr[it2][0], arr[it1][0] = arr[it1][0], arr[it2][0]
                arr[it2][1], arr[it1][1] = arr[it1][1], arr[it2][1]
Len = len(arr)
finalArr = [0] * Len
for p in range(Len - 1, -1, -1):
    finalArr[arr[p][0] - 1] = array[p]
Sum = sum(finalArr)
Ans = 0
for quer in range(b):
    temp = Sum
    for i in range(0, queries[quer][0] - 1):
        temp -= finalArr[i]
    for j in range(queries[quer][1], len(finalArr)):
        temp -= finalArr[j]
    Ans += temp
print(Ans)
