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
from collections import *
sys.setrecursionlimit(10**5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda: next(itr)
def ni(): return int(INP())
def nl(): return [int(_) for _ in INP().split()]



class FenwickTree: # zero indexed calls!
    def __init__(self, sz):
        self.data = [0]*(sz+1)
    def inc(self, i, delta):
        i += 1 # (to 1 indexing)
        while i < len(self.data):
            self.data[i] += delta
            i += i&-i # lowest oneBit
    def sum(self, i):
        i += 1 # (to 1 indexing)
        S = 0
        while i > 0:
            S += self.data[i]
            i -= i&-i
        return S
    def query(self, lo, hi):
        return self.sum(hi) - self.sum(lo)
    

n, quer = nl()
a = nl()
tree = FenwickTree(n+2)
for _ in range(quer):
    l, r = nl()
    tree.inc(l,1)
    tree.inc(r+1,-1)
#now we have a tree that jhas the amount of times each thing was added
#test
#print(a)
a.sort()
appeareances = []
for i in range(1,n+1):
    appeareances.append(tree.sum(i))
    
appeareances.sort()
tot = 0
for i in range(1,n+1):
    tot += appeareances[n-i] * a[n-i]

print(tot)
