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.
#!/usr/bin/env python
import os
import sys
import time
from io import BytesIO, IOBase
 
 
def main():
 
    def ans(out, space=True):
        if space:
            print(' '.join(map(str, out)))
        else:
            print(out)

        sys.stdout.flush()
    
    
    line = input()
    nq = line.split(" ")
    n = int(nq[0])
    q = int(nq[1])

    data = input().split(" ")
    data.sort()

    diff = [0] * n
    for i in range(q):
        query = input()
        d = query.split(" ")
        first = int(d[0]) - 1
        second = int(d[1])
        diff[first] += 1
        if second < n:
            diff[second] -= 1

    output = [0] * n
    output[0] = diff[0]
    for i in range(1, n):
        output[i] = output[i-1] + diff[i]

    output.sort()
    r = 0
    for i in range(n):
        r += output[i] * int(data[i])


    ans(r, False)


 
 
############
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
# def print(*args, **kwargs):
#     """Prints the values to a stream, or to sys.stdout by default."""
#     sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
#     at_start = True
#     for x in args:
#         if not at_start:
#             file.write(sep)
#         file.write(str(x))
#         at_start = False
#     file.write(kwargs.pop("end", "\n"))
#     if kwargs.pop("flush", False):
#         file.flush()
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
 
 
def input():
    return sys.stdin.readline().rstrip("\r\n")
 
 
def i_input():
    return int(input())
 
 
def l_input():
    return input().split()
 
 
def li_input():
    return list(map(int, l_input()))
 
 
def il_input():
    return list(map(int, l_input()))
 
 
# endregion
 
if __name__ == "__main__":
    TT = time.time()
    main()
    # print("\n", time.time() - TT)