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.
import sys
input = sys.stdin.readline

n,k = map(int, input().split())
arr = list(map(int, input().split()))

def func(a, b):
    return a + b


class Tree:
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self.init(arr, 0, self.n - 1, 1)

    def init(self, arr, left, right, node):
        if left == right:
            self.arr[node] = arr[left]
            return self.arr[node]
        mid = (left + right) // 2
        l = self.init(arr, left, mid, node * 2)
        r = self.init(arr, mid + 1, right, node * 2 + 1)
        self.arr[node] = func(l,r)
        return self.arr[node]

    def propagate(self, node, nodeLeft, nodeRight):
        if self.lazy[node] != 0:
            if nodeLeft != nodeRight:
                self.lazy[node * 2] = func(self.lazy[node * 2], self.lazy[node])
                self.lazy[node * 2 + 1] = func(self.lazy[node * 2 + 1], self.lazy[node])
            self.arr[node] = func(self.arr[node], self.lazy[node] * (nodeRight - nodeLeft + 1))
            self.lazy[node] = 0

    def query(self, left, right):
        return self.query2(left, right, 1, 0, n - 1)

    def query2(self, left, right, node, nodeLeft, nodeRight):
        self.propagate(node, nodeLeft, nodeRight)
        if right < nodeLeft or nodeRight < left:
            return 0
        if left <= nodeLeft and nodeRight <= right:
            return self.arr[node]
        mid = (nodeLeft + nodeRight) // 2
        return func(self.query2(left, right, node * 2, nodeLeft, mid),
                    self.query2(left, right, node * 2 + 1, mid + 1, nodeRight))

    def update(self, left, right, newValue):
        return self.update2(left, right, newValue, 1, 0, n - 1)

    def update2(self, left, right, newValue, node, nodeLeft, nodeRight):
        self.propagate(node, nodeLeft, nodeRight)
        if right < nodeLeft or nodeRight < left:
            return self.arr[node]
        if left <= nodeLeft and nodeRight <= right:
            self.lazy[node] = func(self.lazy[node], newValue)
            self.propagate(node, nodeLeft, nodeRight)
            return self.arr[node]
        mid = (nodeLeft + nodeRight) // 2
        self.arr[node] = func(self.update2(left, right, newValue, node * 2, nodeLeft, mid),
                        self.update2(left, right, newValue, node * 2 + 1, mid + 1, nodeRight))
        return self.arr[node]

st = Tree([0]*n)
for i in range(k):
    a,b=map(int, input().split())
    st.update(a-1,b-1, 1)
cnt = []
for i in range(n):
    cnt.append((st.query(i,i),i))
arr.sort(reverse=True)
cnt.sort(key=lambda x:x[0], reverse = True)
answer = 0
for i in range(n):
    answer += cnt[i][0] * arr[i]
print(answer)