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 ≤ l_{i} ≤ r_{i} ≤ 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.


-----Input-----

The first line contains two space-separated integers n (1 ≤ n ≤ 2·10^5) and q (1 ≤ q ≤ 2·10^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 ≤ a_{i} ≤ 2·10^5) — the array elements.

Each of the following q lines contains two space-separated integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — the i-th query.


-----Output-----

In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
3 3
5 3 2
1 2
2 3
1 3

Output
25

Input
5 3
5 2 4 1 3
1 5
2 3
2 3

Output
33

Difficulty: interview

Starter code:

Solutions:
n,q=list(map(int,input().split()))

A=list(map(int,input().split()))


C=[0]*n

for i in range(q):
    l,r=list(map(int,input().split()))
    C[l-1]+=1
    if(r!=n):
        C[r]-=1


for i in range(1,n):
    C[i]+=C[i-1]

C.sort()
A.sort()

ans=0
for i in range(n):
    ans+=C[i]*A[i]
print(int(ans))


n, q = map(int, input().split())
t = [0] + list(map(int, input().split()))
p = [0] * (n + 1)

for i in range(q):
    l, r = map(int, input().split())
    p[l - 1] += 1
    p[r] -= 1

for i in range(1, n + 1):
    p[i] += p[i - 1]

t.sort()
p.sort()

print(sum(p[i] * t[i] for i in range(1, n + 1)))

n, q = map(int, input().split())
t = [0] + list(map(int, input().split()))
p = [0] * (n + 1)

for i in range(q):
    l, r = map(int, input().split())
    p[l - 1] += 1
    p[r] -= 1

for i in range(1, n + 1):
    p[i] += p[i - 1]

t.sort()
p.sort()

j = 0
while p[j] == 0: j += 1

print(sum(p[i] * t[i] for i in range(j, n + 1)))

n,q=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*(n+1)
c=[0]*(n)
for i in range(q):
    l,r=map(int,input().split())
    b[l-1]+=1
    b[r]-=1
cur=0
for i in range(n):
    cur+=b[i]
    c[i]=cur
#print(c)
c.sort()
a.sort()
#print(a)
cur=0
for i in range(n):
    cur+=a[i]*c[i]
print(cur)

n,q=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*(n+1)
c=[0]*(n)
for i in range(q):
    l,r=map(int,input().split())
    b[l-1]+=1
    b[r]-=1
cur=0
for i in range(n):
    cur+=b[i]
    c[i]=cur
c.sort()
a.sort()
cur=0
for i in range(n):
    cur+=a[i]*c[i]
print(cur)

def main():
    import sys
    data = [int(i) for i in sys.stdin.read().split()]
    data.reverse()
    
    n, q = data.pop(), data.pop()
    arr = [data.pop() for i in range(n)]
    arr.sort()
    
    S = [0 for i in range(n + 1)]
    for i in range(q):
        l, r = data.pop(), data.pop()
        S[r] += 1
        S[l - 1] -= 1
    
    d = [0 for i in range(n)]
    count = 0
    for i in reversed(list(range(n))):
        count += S[i + 1]
        d[i] = count
    d.sort()
    
    result = 0
    for i in range(n):
        result += d[i] * arr[i]
    
    print(result)

main()


import sys
data = [int(i) for i in sys.stdin.read().split()]
data.reverse()

n1,n2 = data.pop(), data.pop()
a = sorted([data.pop() for i in range(n1)],reverse=True)

# n = list(map(int,input().split()))
# a = sorted(list(map(int,input().split())),reverse=True)
check = [0]*(n1+1) # Массив для указателей на отметки, между которыми происходит заполнение
result = [0]*n1 # Массив содержащий лучшее расположение элементов
for i in range(n2):
    temp1,temp2 = data.pop(), data.pop()
    check[temp1-1] += 1 # Указатели на отметки для заполнения
    check[temp2] -= 1
temp = 0
for i in range(n1):
    temp += check[i]
    result[i] = temp
result.sort(reverse=True)
sum = 0
for i in range(n1): sum+=result[i]*a[i]
print(sum)

n, q = map(int, input().split())
arr = list(map(int, input().split()))
pref = [0 for _ in range(n)]

for _ in range(q):
	l, r = map(int, input().split())
	pref[l-1] += 1
	if r < n:
		pref[r] -= 1

lol = []
cur = 0
for i in range(n):
	cur += pref[i]
	lol.append(cur)
lol.sort()
arr.sort()

ans = 0
for i in range(n-1,-1,-1):
	ans += arr[i] * lol[i]
print(ans)

N, Q = map(int, input().split())
array = list(map(int, input().split()))
array.sort()

count = [0 for i in range(N+1)]

for q in range(Q):
    l, r = map(int, input().split())
    count[l-1] += 1
    count[r] -= 1

for i in range(1, N):
    count[i] += count[i-1]
count.sort()

res = 0
for i in range(N):
    res += count[i+1] * array[i]

print(res)

def main():
    n, m = list(map(int, input().split()))
    aa = sorted(map(int, input().split()))
    bb = [0] * (n + 1)
    for _ in range(m):
        l, r = list(map(int, input().split()))
        bb[l - 1] += 1
        bb[r] -= 1
    a = 0
    for i, b in enumerate(bb):
        a += b
        bb[i] = a
    del bb[-1]
    bb.sort()
    print(sum(a * b for a, b in zip(aa, bb)))


def __starting_point():
    main()

__starting_point()

#in the name of god
#Mr_Rubick
n,q=list(map(int,input().split()))
t=[0]+list(map(int,input().split()))
p=[0]*(n+1)
for i in range(q):
    l,r=list(map(int,input().split()))
    p[l-1]+=1
    p[r]-=1
for i in range(1,n+1):
    p[i]+=p[i-1]
t.sort()
p.sort()
cnt=0
while p[cnt]==0:
    cnt+=1
print(sum(p[i]*t[i] for i in range(cnt,n+1)))


import sys
n,q=list(map(int, sys.stdin.readline().split()))
l1=[0]+list(map(int, sys.stdin.readline().split()))
l1.sort()
b=[]
for i in range(0,n+2):
    b.append(0)
for jj in range(0,q):
    l,r=list(map(int, sys.stdin.readline().split()))
    b[l]+=1
    b[r+1]-=1
for i in range(2,n+1):
    b[i]+=b[i-1]    
b.sort()
sum1=0
k=len(b)
k-=1
kk=n
for i in range(1,n+1):
    sum1+=(b[k]*l1[kk])
    k-=1
    kk-=1
print(sum1)    


#python3
import sys, threading, os.path
import collections, heapq, math,bisect
import string
from platform import python_version
import itertools
sys.setrecursionlimit(10**6)
threading.stack_size(2**27)     

def main():
    if os.path.exists('input.txt'):
        input = open('input.txt', 'r')
    else:
        input = sys.stdin
    #--------------------------------INPUT---------------------------------
    n,q = list(map(int, input.readline().split()))
    lis = list(map(int, input.readline().split()))
    lis.sort()
    val = [0]*(n+1)
    for i in range(q):
        l,r = list(map(int, input.readline().split()))
        val[l-1] += 1
        val[r] -= 1
    for i in range(n):
        val[i+1]+=val[i]
    val.sort()
    sum=0
    for i in range(n):
        sum+=val[i+1]*lis[i]
    output = sum
    #-------------------------------OUTPUT----------------------------------
    if os.path.exists('output.txt'):
        open('output.txt', 'w').writelines(str(output))
    else:
        sys.stdout.write(str(output))


def __starting_point():
    main()
#threading.Thread(target=main).start()

__starting_point()

#python 3.5.2

n, q = list(map(int, input().split()))
arr = list(map(int, input().split()))
arr.sort()
occ = [0] * n

for i in range(q):
    l, r = list(map(int, input().split()))
    occ[l-1]+=1
    if (r < n): occ[r]-=1
    
for i in range(1,n):
    occ[i]+=occ[i-1]
occ.sort()    
    
sum = 0
for i in range(n):
    sum += arr[i] * occ[i]

print (sum)


#python 3.5.2

n,q = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
arr.sort()
occ = [0] * n

for i in range(q):
    l, r = list(map(int, input().split()))
    occ[l-1]+=1
    if (r < n): occ[r]-=1
    
for i in range(1,n):
    occ[i]+=occ[i-1]
occ.sort()    
    
sum = 0
for i in range(n):
    sum += arr[i] * occ[i]

print (sum)


import sys
input=sys.stdin.readline
print=sys.stdout.write
n,q=map(int,input().split())
ar=list(map(int,input().split()))
qs=[map(int,input().split()) for x in range(q)]
s=[0]*n
def f(l,r):
    s[l]+=1
    if r < n:
        s[r]-=1
for x in range(q):
    a,b=qs[x]
    a-=1
    f(a,b)
d=[s[0]]
for x in range(1,n):
    s[x]+=s[x-1]
    d.append(s[x])
ar=sorted(ar)
d=sorted(d)[::-1]
sm=0
for x in range(n):
    sm+=ar[x]*d[n-x-1]
print(str(sm))

import sys
data = [int(i) for i in sys.stdin.read().split()]
data.reverse()
def read(): return data.pop()

n, q = read(), read()
A = [read() for i in range(n)]
F = [0] * (n+5)

for i in range(q) :
	l, r = read(), read()
	F[l] += 1
	F[r+1] -= 1

for i in range(1, n+1) :
    F[i] += F[i-1]

A.sort()	
F = sorted(F[1:n+1])

ans = 0
for i in range(n) :
    ans += A[i] * F[i]
    
print(ans)

n,q=list(map(int,input().split()))

a=list(map(int,input().split()))

b=[0]*(n+1)

c=[0]*(n)

for i in range(q):

    l,r=list(map(int,input().split()))

    b[l-1]+=1

    b[r]-=1

cur=0

for i in range(n):

    cur+=b[i]

    c[i]=cur

c.sort()

a.sort()

cur=0

for i in range(n):

    cur+=a[i]*c[i]

print(cur)



# Made By Mostafa_Khaled


num_elements, num_queries = list(map(int, input().split()))
elements = list(map(int, input().split()))
elements.sort(reverse=True)
occurrences = [0]*(num_elements + 2)
for _ in range(num_queries):
    l, r = list(map(int, input().split()))
    occurrences[l] += 1
    occurrences[r+1] -= 1
for pos in range(1,num_elements + 1):
    occurrences[pos] += occurrences[pos - 1]
occurrences.sort(reverse=True)
solution = 0
for pos in range(num_elements):
    solution += occurrences[pos] * elements[pos]
print(solution)


import sys
data = [int(i) for i in sys.stdin.read().split()]
data.reverse()
def read(): return data.pop()

n, q = read(), read()
A = [read() for i in range(n)]
F = [0] * (n+5)

for i in range(q) :
	l, r = read(), read()
	F[l] += 1
	F[r+1] -= 1

for i in range(1, n+1) :
    F[i] += F[i-1]

A.sort()	
F = sorted(F[1:n+1])

ans = 0
for i in range(n) :
    ans += A[i] * F[i]
    
print(ans)

def solve():
    n, q = list(map(int, input().split()))

    a = list(map(int, input().split()))
    a.sort(reverse=True)

    w = [0 for i in range(n+2)]
    
    for query in range(q):
        l, r = list(map(int, input().split()))
        w[l] += 1
        w[r+1] -= 1

    for i in range(2, n+1):
        w[i] += w[i-1]

    w.sort(reverse=True)

    maxSum = 0
    for i in range(n):
        maxSum += a[i]*w[i]
        if w[i] == 0:
            break

    print(maxSum)

def __starting_point():
    solve()

__starting_point()

def solve():
    n, q = list(map(int, input().split()))

    a = list(map(int, input().split()))
    a.sort(reverse=True)

    w = [0 for i in range(n+2)]
    
    for query in range(q):
        l, r = list(map(int, input().split()))
        w[l] += 1
        w[r+1] -= 1

    for i in range(2, n+1):
        w[i] += w[i-1]

    w.sort(reverse=True)

    maxSum = 0
    for i in range(n):
        maxSum += a[i]*w[i]

    print(maxSum)

def __starting_point():
    solve()

__starting_point()

n,q= list(map(int,input().strip().split()))
arr = list(map(int,input().strip().split()))
arr.sort(reverse=True)
b = [0] *(n+2)
z = [0] * (n+2);
s  = 0
for x in range(q):
    l,r = list(map(int,input().strip().split()))
    b[l] += 1
    b[r+1] -= 1
# print(b)
for x in range(1,n+1):
    z[x] = z[x-1]+b[x]
# print(z)
z.sort(reverse=True)
for x in range(n):
    s += z[x] * arr[x]
print(s)