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

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Data structures

Implementation

Greedy algorithms


Solutions:
from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
l = list(map(int, stdin.readline().split()))
l1 = [0] * n
for i in range(m):
	(p, q) = map(int, stdin.readline().split())
	l1[p - 1] += 1
	if q != n:
		l1[q] -= 1
c = 0
for i in range(n):
	c += l1[i]
	l1[i] = c
l1.sort()
l.sort()
a = 0
for i in range(n):
	a += l[i] * l1[i]
stdout.write(str(a) + '\n')


inp = lambda : map(int, input().rstrip().split())
(n, q) = inp()
li = sorted(inp())
a = [0] * (n + 1)
for _ in range(q):
	(x, y) = inp()
	a[x - 1] += 1
	a[y] -= 1
for i in range(n):
	a[i + 1] += a[i]
print(sum(map(lambda x: x[0] * x[1], zip(li, sorted(a[:-1])))))


(n, q) = map(int, input().split(' '))
nums = [int(x) for x in input().split(' ')]
changes = [0] * (n + 1)
for i in range(q):
	(l, r) = map(int, input().split(' '))
	changes[l - 1] += 1
	changes[r] -= 1
mlts = [0] * n
cur_layers = 0
for i in range(n):
	cur_layers += changes[i]
	mlts[i] = cur_layers
mlts.sort()
nums.sort()
res = 0
for i in range(n):
	res += mlts[i] * nums[i]
print(res)


from bisect import bisect
from collections import defaultdict
from math import gcd, sqrt, ceil, inf
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 9)

def update(i, z, bit):
	while i < len(bit):
		bit[i] += z
		i += i & -i

def query(i, bit):
	sum = 0
	while i > 0:
		sum += bit[i]
		i -= i & -i
	return sum
hash = defaultdict(int)
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
c = [0] * (n + 1)
for i in range(q):
	(l1, r1) = map(int, input().split())
	c[l1] += 1
	if r1 + 1 < len(c):
		c[r1 + 1] -= 1
for i in range(1, n + 1):
	c[i] += c[i - 1]
c.sort()
l.sort()
ans = 0
for i in range(1, n + 1):
	ans += l[i - 1] * c[i]
print(ans)


import os, sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil
mod = 10 ** 9 + 7
for _ in range(1):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	count_queries = [[0, i] for i in range(n + 1)]
	for i in range(q):
		(l, r) = map(int, input().split())
		if r == n:
			count_queries[l][0] += 1
		else:
			count_queries[l][0] += 1
			count_queries[r + 1][0] -= 1
	for i in range(2, n + 1):
		count_queries[i][0] += count_queries[i - 1][0]
	count_queries.sort()
	max_possible_sum = 0
	for i in range(n, 0, -1):
		max_possible_sum += count_queries[i][0] * a.pop()
	print(max_possible_sum)


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
(n, q) = I()
l = I()
l.sort(reverse=True)
a = []
c = [0] * 200005
for i in range(q):
	(x, y) = I()
	x -= 1
	y -= 1
	a.append([x, y])
	c[x] += 1
	c[y + 1] -= 1
for i in range(200005):
	c[i] += c[i - 1]
for i in range(200005):
	c[i] = [c[i], i]
c.sort(reverse=True)
arr = [0] * 2000005
for i in range(n):
	arr[c[i][1]] = l[i]
arr += [0]
for i in range(1, n):
	arr[i] += arr[i - 1]
ans = 0
for i in a:
	ans += arr[i[1]] - arr[i[0] - 1]
print(ans)


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)


(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))))


(n, q) = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort(reverse=True)
d = [0] * (n + 1)
maximum = 0
for i in range(q):
	(l, r) = map(int, input().split())
	d[l - 1] += 1
	d[r] -= 1
for i in range(1, n):
	d[i] += d[i - 1]
d.sort(reverse=True)
for i in range(n):
	maximum += nums[i] * d[i]
print('{}'.format(maximum))


import os
import sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	(n, q) = map(int, input().split())
	vals = sorted(map(int, input().split()))
	check = [0] * n
	for s in range(q):
		(l, r) = map(int, input().split())
		check[l - 1] += 1
		if r < n:
			check[r] -= 1
	for s in range(1, n):
		check[s] += check[s - 1]
	check.sort()
	ans = 0
	for s in range(n - 1, -1, -1):
		ans += vals.pop() * check[s]
	print(ans)
main()


(n, m) = map(int, input().split())
data = list(map(int, input().split()))
mat = [list(map(int, input().split())) for _ in range(m)]
cnt = [0] * n
for (start, end) in mat:
	start -= 1
	cnt[start] += 1
	if end < n:
		cnt[end] -= 1
prev = 0
for idx in range(n):
	cnt[idx] += prev
	prev = cnt[idx]
cnt.sort()
data.sort()
print(sum((a * b for (a, b) in zip(data, cnt))))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l1 = [0] * n
for i in range(m):
	(p, q) = map(int, input().split())
	l1[p - 1] += 1
	if q != n:
		l1[q] -= 1
c = 0
for i in range(n):
	c += l1[i]
	l1[i] = c
l.sort()
l1.sort()
s = 0
for i in range(n):
	s += l[i] * l1[i]
print(s)


import sys
input = sys.stdin.readline

def read():
	return map(int, input().split())
(n, q) = read()
a = [0] + list(read())
d = [0] * (n + 2)
for _ in range(q):
	(li, ri) = read()
	d[li] += 1
	d[ri + 1] -= 1
s = 0
b = [0] * (n + 1)
for i in range(1, n + 1):
	s += d[i]
	b[i] = s
a.sort()
b.sort()
ans = 0
for i in range(1, n + 1):
	ans += a[i] * b[i]
print(ans)


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(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

def answer(n, q, a, l, r):
	freq1 = [0 for _ in range(n + 2)]
	for i in range(q):
		freq1[l[i]] += 1
		freq1[r[i] + 1] -= 1
	freq2 = [0 for _ in range(n + 2)]
	for i in range(1, n + 2):
		freq2[i] = freq2[i - 1] + freq1[i]
	freq2.sort(reverse=True)
	a.sort(reverse=True)
	ans = 0
	for i in range(n):
		ans += a[i] * freq2[i]
	return ans

def main():
	(n, q) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	l = [0 for _ in range(q)]
	r = [0 for _ in range(q)]
	for i in range(q):
		(l[i], r[i]) = map(int, sys.stdin.readline().split())
	print(answer(n, q, a, l, r))
	return
main()


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
arr = [0 for _ in range(n + 2)]
a.sort(reverse=True)
for _ in range(q):
	(l, r) = map(int, input().split())
	arr[l] += 1
	arr[r + 1] -= 1
for i in range(1, n + 1):
	arr[i] += arr[i - 1]
arr.sort(reverse=True)
ans = 0
for i in range(n):
	ans += a[i] * arr[i]
print(ans)


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = [0 for i in range(n)]
for i in range(q):
	(l, r) = map(int, input().split())
	ans[l - 1] += 1
	if r != n:
		ans[r] -= 1
for i in range(1, n):
	ans[i] = ans[i - 1] + ans[i]
sum = 0
ans.sort(reverse=True)
for i in range(n):
	sum += ans[i] * a[i]
print(sum)


(n, q) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
freq = [0] * n
for i in range(q):
	(l, r) = [int(x) for x in input().split()]
	l -= 1
	r -= 1
	freq[l] += 1
	if r + 1 < n:
		freq[r + 1] -= 1
for i in range(1, n):
	freq[i] += freq[i - 1]
freq.sort()
arr.sort()
ans = 0
for i in range(n):
	ans += freq[i] * arr[i]
print(ans)


import sys
import functools
(n, q) = [int(x) for x in sys.stdin.readline().strip().split()]
arr = [int(x) for x in sys.stdin.readline().strip().split()]
query = []
p = [0] * (n + 2)
for i in range(q):
	(l, r) = [int(x) for x in sys.stdin.readline().strip().split()]
	query.append([l, r])
	p[l] += 1
	p[r + 1] -= 1
for i in range(1, n + 2):
	p[i] += p[i - 1]
p = p[:-1]
arr = [0] + arr
s_index = list(range(n + 1))
s = sorted(s_index, key=lambda x: p[x] * 10 ** 6 + x)
arr = sorted(arr)
new_arr = [0] * (n + 1)
for (i, j) in enumerate(s):
	new_arr[j] = arr[i]
for i in range(1, n + 1):
	new_arr[i] += new_arr[i - 1]
s = 0
for (i, j) in query:
	s += new_arr[j] - new_arr[i - 1]
print(s)


(num_elements, num_queries) = 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) = 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 math
import bisect
import itertools
import sys
I = lambda : sys.stdin.readline()
one = lambda : int(I())
more = lambda : map(int, I().split())
linput = lambda : list(more())
mod = 10 ** 9 + 7
inf = 10 ** 18 + 1

def merge(a, b):
	i = 0
	j = 0
	c = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			c += len(a) - i
			j += 1
	ans += a[i:]
	ans += b[j:]
	return (ans, c)

def mergesort(a):
	if len(a) == 1:
		return (a, 0)
	mid = len(a) // 2
	(left, left_inversion) = mergesort(a[:mid])
	(right, right_inversion) = mergesort(a[mid:])
	(m, c) = merge(left, right)
	c += left_inversion + right_inversion
	return (m, c)

def is_prime(num):
	if num == 1:
		return False
	if num == 2:
		return True
	if num == 3:
		return True
	if num % 2 == 0:
		return False
	if num % 3 == 0:
		return False
	t = 5
	a = 2
	while t <= int(math.sqrt(num)):
		if num % t == 0:
			return False
		t += a
		a = 6 - a
	return True

def ceil(a, b):
	return (a + b - 1) // b
(n, q) = more()
a = [0] + linput()
diff = [0] * (n + 2)
for i in range(q):
	(x, y) = more()
	diff[x] += 1
	diff[y + 1] -= 1
for i in range(1, n + 2):
	diff[i] += diff[i - 1]
a.sort()
ans = 0
diff.sort()
for i in range(n):
	ans += a[-1 - i] * diff[-i - 1]
print(ans)


(n, m) = map(int, input().split())
arr = sorted(list(map(int, input().split())))
seg = [list(map(int, input().split())) for _ in range(m)]
(cnt, res) = ([0] * (n + 1), 0)
for (i, j) in seg:
	cnt[i - 1] += 1
	cnt[j] -= 1
for i in range(1, n):
	cnt[i] += cnt[i - 1]
cnt = sorted(cnt[:n])
for i in range(n):
	res += cnt[i] * arr[i]
print(res)


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


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


(n, q) = map(int, input().split())
l = [int(x) for x in input().split()]
pre = [0] * n
for _ in range(q):
	(a, b) = map(int, input().split())
	pre[a - 1] += 1
	if b != n:
		pre[b] -= 1
p = []
temp = 0
for i in pre:
	temp += i
	p.append(temp)
l.sort()
p.sort()
ans = 0
for i in range(n):
	ans += l[i] * p[i]
print(ans)


from sys import stdin
input = stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
sumDiff = [0] * (n + 1)
for _ in range(q):
	(l, r) = map(int, input().split())
	sumDiff[l - 1] += 1
	sumDiff[r] -= 1
for i in range(1, n):
	sumDiff[i] += sumDiff[i - 1]
sumDiff.sort(reverse=True)
pntr = 0
maxSum = 0
for pntr in range(n):
	maxSum += sumDiff[pntr] * a[pntr]
print(maxSum)


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def pr_list(a):
	print(*a, sep=' ')

def main():
	[n, q] = inlt()
	values = inlt()
	slots = []
	values.sort(reverse=True)
	for i in range(q):
		[l, r] = inlt()
		slots.append([l, r])
	dum = [0 for i in range(n)]
	for i in slots:
		dum[i[0] - 1] = dum[i[0] - 1] + 1
		if i[1] < n:
			dum[i[1]] = dum[i[1]] - 1
	curr = 0
	for i in range(n):
		curr = curr + dum[i]
		dum[i] = curr
	dum.sort(reverse=True)
	out = 0
	for i in range(n):
		out = out + dum[i] * values[i]
	print(out)
	return
main()


import itertools
(n, q) = map(int, input().split())
b = list(sorted(map(int, input().split())))
a = [0] * (n + 1)
for _ in range(q):
	(l, r) = map(int, input().split())
	a[l - 1] += 1
	a[r] -= 1
a = list(sorted(itertools.accumulate(a)))
summa = 0
i = n
while i > 0:
	summa += a[i] * b[i - 1]
	i -= 1
print(summa)


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()


fast = lambda : stdin.readline().strip()
zzz = lambda : [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))
from re import *
from sys import *
from math import *
from heapq import *
from queue import *
from bisect import *
from string import *
from itertools import *
from collections import *
from math import factorial as f
from bisect import bisect as bs
from bisect import bisect_left as bsl
from collections import Counter as cc
from itertools import accumulate as ac

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer):
	stdout.write(str(answer))
(n, q) = zzz()
arr = szzz()
lst = [0] * n
for i in range(q):
	(l, r) = zzz()
	lst[l - 1] += 1
	if r < n:
		lst[r] -= 1
for i in range(1, n):
	lst[i] += lst[i - 1]
lst.sort()
print(sum((arr[i] * lst[i] for i in range(n))))


(n, q) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
a.sort(reverse=True)
b = [0] * (n + 2)
for _ in range(q):
	(l, r) = map(int, input().split(' '))
	b[l] += 1
	b[r + 1] -= 1
op = 0
maxop = 0
c = [0] * (max(n, q) + 1)
for bi in b:
	op += bi
	c[op] += 1
	maxop = max(op, maxop)
w = 0
sol = 0
for i in range(maxop):
	for j in range(c[maxop - i]):
		sol += a[w] * (maxop - i)
		w += 1
print(sol)


(n, q) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
fr = [0 for i in range(0, n + 2)]
for i in range(0, q):
	(l, r) = [int(x) for x in input().split()]
	fr[l] += 1
	fr[r + 1] -= 1
for i in range(1, n + 2):
	fr[i] += fr[i - 1]
fr.sort(reverse=True)
a.sort(reverse=True)
max_sum = 0
for i in range(0, n):
	max_sum += a[i] * fr[i]
print(max_sum)


(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))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C, OrderedDict as od
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
(n, q) = sp()
arr = l()
dp = [0] * (n + 1)
for _ in range(q):
	(l, r) = sp()
	dp[l - 1] += 1
	dp[r] -= 1
for i in range(1, n + 1):
	dp[i] += dp[i - 1]
arr.sort(reverse=True)
dp.sort(reverse=True)
answer = 0
for i in range(n):
	answer += dp[i] * arr[i]
out(answer)


from sys import maxsize, stdout, stdin, stderr
mod = int(1e+20 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 1
	right = x
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	if n > 2:
		l.append(n)
	return l
(n, q) = lint()
s = lint()
ans = 0
e = [0] * n
s.sort(reverse=True)
for _ in range(q):
	(l, r) = lint()
	e[l - 1] += 1
	if r != n:
		e[r] -= 1
for i in range(1, n):
	e[i] += e[i - 1]
ans = 0
e.sort(reverse=True)
for i in range(n):
	ans += e[i] * s[i]
print(ans)


I = lambda : int(input())
IL = lambda : list(map(int, input().split()))
(n, q) = IL()
A = IL()
Q = [IL() for _ in range(q)]
T = [0] * (n + 2)
for (a, b) in Q:
	T[a] += 1
	T[b + 1] -= 1
for i in range(1, n + 2):
	T[i] = T[i - 1] + T[i]
print(sum((a * b for (a, b) in zip(sorted(A)[::-1], sorted(T)[::-1]))))


(n, q) = map(int, input().split())
ls = [int(a) for a in input().split()]
(ls1, ls2, ls3) = ([0] * n, [0] * n, [0] * n)
ls.sort(reverse=True)
for i in range(q):
	(l, r) = map(int, input().split())
	ls1[l - 1] += 1
	ls2[r - 1] += 1
s = 0
for i in range(n):
	s += ls1[i]
	ls3[i] = s
	s -= ls2[i]
ls3.sort(reverse=True)
ans = 0
for i in range(n):
	if ls3[i] == 0:
		break
	ans += ls[i] * ls3[i]
print(ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
l = [0] * (n + 2)
for i in range(m):
	(x, y) = map(int, input().split())
	l[x] += 1
	l[y + 1] -= 1
for i in range(2, n + 2):
	l[i] += l[i - 1]
l.sort(reverse=True)
a.sort(reverse=True)
ans = 0
for i in range(n):
	ans += l[i] * a[i]
print(ans)


from sys import stdin, stdout

def fastInput():
	return stdin.readline()

def fastPrint(s):
	return stdout.write('%s\n' % s)
(n, q) = map(int, fastInput().split())
a = list(map(int, fastInput().split()))
queries = [tuple(map(lambda x: int(x) - 1, fastInput().split())) for _ in range(q)]

def sumRange(left, right):
	return psums[right + 1] - psums[left]
add = [0] * (n + 1)
for (left, right) in queries:
	add[left] += 1
	add[right + 1] -= 1
freq = []
curSum = 0
for i in range(n):
	curSum += add[i]
	freq.append((i, curSum))
freq.sort(key=lambda x: -x[1])
a.sort(reverse=True)
best = [0] * n
for (i, (pos, _)) in enumerate(freq):
	best[pos] = a[i]
psums = [0]
for val in best:
	psums.append(psums[-1] + val)
ret = 0
for (left, right) in queries:
	ret += sumRange(left, right)
fastPrint(str(ret))


from sys import stdin
(n, q) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
c = [0 for i in range(n + 1)]
for _ in range(q):
	(l, r) = map(int, stdin.readline().split())
	c[l - 1] += 1
	c[r] -= 1
curr = 0
b = []
for i in range(n):
	curr += c[i]
	b.append((curr, i))
b.sort()
a.sort()
sol = 0
for i in range(n):
	sol += b[i][0] * a[i]
print(sol)


(n, q) = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
queries = []
for _ in range(q):
	queries.append(list(map(int, input().split())))
dp = [0] * (n + 1)
for (x, y) in queries:
	dp[x - 1] += 1
	dp[y] -= 1
for i in range(1, n + 1):
	dp[i] += dp[i - 1]
dp.sort(reverse=True)
res = 0
for i in range(n):
	res += dp[i] * a[i]
print(res)


from sys import stdin
input = stdin.readline
R = lambda : map(int, input().split())
(n, q) = R()
a = sorted(R())
b = [0] * n
for _ in range(q):
	(x, y) = R()
	b[x - 1] += 1
	if y < n:
		b[y] -= 1
for i in range(1, n):
	b[i] += b[i - 1]
b.sort()
print(sum((a[i] * b[i] for i in range(n))))


def initializeDiffArray(A):
	n = len(A)
	D = [0 for i in range(0, n + 1)]
	D[0] = A[0]
	D[n] = 0
	for i in range(1, n):
		D[i] = A[i] - A[i - 1]
	return D

def update(D, l, r, x):
	D[l] += x
	D[r + 1] -= x

def printArray(A, D):
	for i in range(0, len(A)):
		if i == 0:
			A[i] = D[i]
		else:
			A[i] = D[i] + A[i - 1]
import sys, math, string
input = sys.stdin.readline
from collections import deque
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
h = [0] * n
d = initializeDiffArray(h)
for i in range(q):
	(a, b) = map(int, input().split())
	update(d, a - 1, b - 1, 1)
printArray(h, d)
h.sort(reverse=True)
l.sort(reverse=True)
p = 0
for i in range(n):
	if h[i] == 0:
		break
	p += h[i] * l[i]
print(p)


(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)


import sys, os, io
from sys import stdin
import math
from collections import defaultdict
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase
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')
alphabets = list('abcdefghijklmnopqrstuvwxyz')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
	(n, q) = li()
	a = li()
	cnt = [0] * (n + 3)
	for i in range(q):
		(l, r) = li()
		cnt[l] += 1
		cnt[r + 1] -= 1
	a.sort(reverse=True)
	for i in range(1, len(cnt)):
		cnt[i] += cnt[i - 1]
	cnt1 = []
	for i in range(len(cnt)):
		cnt1.append([cnt[i], i])
	cnt1.sort(reverse=True)
	ans = 0
	for i in range(n):
		(times, pos) = cnt1[i]
		ans += times * a[i]
	print(ans)
t = 1
for _ in range(t):
	solve()


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
freq = [0 for i in range(n)]
for i in range(k):
	(a, b) = map(int, input().split())
	freq[a - 1] += 1
	if b != n:
		freq[b] -= 1
update = 0
for i in range(n):
	update += freq[i]
	freq[i] = update
freq.sort(reverse=True)
arr.sort(reverse=True)
total = 0
for i in range(n):
	total += freq[i] * arr[i]
print(total)


def main():
	from bisect import bisect_left as bl, bisect_right as br, insort
	import sys, math
	from heapq import heapify, heappush, heappop
	from collections import defaultdict as dd, deque

	def data():
		return sys.stdin.readline().strip()

	def mdata():
		return list(map(int, data().split()))
	out = sys.stdout.write
	INF = int(1000000000.0)
	mod = int(1000000000.0) + 7
	(n, q) = mdata()
	A = mdata()
	lis = [0] * (n + 2)
	for i in range(q):
		(l, r) = mdata()
		lis[l] += 1
		lis[r + 1] -= 1
	for i in range(1, n + 1):
		lis[i] += lis[i - 1]
	lis = lis[1:n + 1]
	A.sort()
	lis.sort()
	ans = 0
	for i in range(n):
		ans += A[i] * lis[i]
	print(ans)
main()


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
	(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
	if os.path.exists('output.txt'):
		open('output.txt', 'w').writelines(str(output))
	else:
		sys.stdout.write(str(output))

def __starting_point():
	main()
__starting_point()


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


(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
for x in range(1, n + 1):
	z[x] = z[x - 1] + b[x]
z.sort(reverse=True)
for x in range(n):
	s += z[x] * arr[x]
print(s)


from sys import stdin
input = stdin.readline
(n, q) = map(int, input().split())
a = sorted(map(int, input().split()))
b = [0] * n
for i in range(q):
	(l, r) = map(int, input().split())
	b[l - 1] += 1
	if r < n:
		b[r] -= 1
for i in range(1, n):
	b[i] += b[i - 1]
b.sort()
print(sum((a[i] * b[i] for i in range(n))))


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import *
from collections import defaultdict, deque, Counter
import math, string
from heapq import *
from operator import add
from itertools import accumulate
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inf = float('inf')
en = lambda x: list(enumerate(x))
ceil_ = lambda a, b: (a + b - 1) // b
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
(n, k) = r()
arr = rr()
arr.sort(reverse=1)
brr = [0] * (n + 1)
for _ in ' ' * k:
	(a, b) = r()
	brr[a - 1] += 1
	brr[b] -= 1
for i in range(1, n + 1):
	brr[i] += brr[i - 1]
brr = brr[:-1]
brr.sort(reverse=1)
c = sum((i * j for (i, j) in zip(arr, brr)))
print(c)


import os, sys, atexit
from io import BytesIO, StringIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
_OUTPUT_BUFFER = StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
(n, q) = [int(x) for x in input().split()]
a = list(map(int, input().split()))
ind = [0] * (n + 1)
while q:
	q -= 1
	(l, r) = map(int, input().split())
	ind[l - 1] += 1
	ind[r] -= 1
for i in range(1, n):
	ind[i] = ind[i - 1] + ind[i]
a.sort(reverse=True)
ind.sort(reverse=True)
s = 0
for i in range(n):
	s += ind[i] * a[i]
print(s)


(a, b) = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l)
arr = [0] * a
sum = 0
for i in range(b):
	(x, y) = map(int, input().split())
	arr[x - 1] += 1
	if y < a:
		arr[y] -= 1
for i in range(1, a):
	arr[i] += arr[i - 1]
arr.sort()
for i in range(a):
	sum += l[i] * arr[i]
print(sum)


inp = lambda : map(int, input().rstrip().split())
(n, q) = inp()
li = sorted(inp())
a = [0] * (n + 1)
for _ in range(q):
	(x, y) = inp()
	a[x - 1] += 1
	a[y] -= 1
for i in range(n):
	a[i + 1] += a[i]
a.sort()
t = 0
for i in range(n):
	t += a[i + 1] * li[i]
print(t)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
dif = [0] * (n + 5)
for x in range(q):
	(a, b) = map(int, input().split())
	dif[a - 1] += 1
	dif[b] -= 1
c = 0
for x in range(len(dif)):
	c += dif[x]
	dif[x] = c
dif.sort(reverse=True)
arr.sort(reverse=True)
c = 0
for x in range(n):
	c += arr[x] * dif[x]
print(c)


import math as mt
import os
import sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, q) = map(int, input().split())
b = list(map(int, input().split()))
a = [0] * n
for j in range(q):
	(l, r) = map(int, input().split())
	a[l - 1] += 1
	if r < n:
		a[r] += -1
j = 1
while j < n:
	a[j] += a[j - 1]
	j += 1
b.sort(reverse=True)
a.sort(reverse=True)
j = 0
s = 0
while j < n:
	s += b[j] * a[j]
	j += 1
print(s)


import sys
input = sys.stdin.buffer.readline

def I():
	return list(map(int, input().split()))

def sieve(n):
	a = [1] * n
	for i in range(2, n):
		if a[i]:
			for j in range(i * i, n, i):
				a[j] = 0
	return a
(n, q) = I()
arr = I()
weights = [0] * (n + 1)
for i in range(q):
	(l, r) = I()
	weights[l - 1] += 1
	weights[r] -= 1
curr = 0
for i in range(n):
	curr += weights[i]
	weights[i] = curr
idxs = list(range(n))
idxs.sort(key=lambda x: weights[x])
arr.sort()
ans = [-1] * n
j = n - 1
s = 0
for i in reversed(idxs):
	ans[i] = arr[j]
	s += weights[i] * arr[j]
	j -= 1
print(s)


def solve():
	(n, q) = list(map(int, input().split(' ')))
	nums = sorted(map(int, input().split(' ')))
	arr = [0] * (n + 1)
	for i in range(q):
		(l, r) = list(map(int, input().split(' ')))
		arr[l - 1] += 1
		arr[r] -= 1
	index = 0
	while index < len(arr) - 1:
		arr[index + 1] += arr[index]
		index += 1
	arr.pop(len(arr) - 1)
	arr.sort()
	index = len(nums) - 1
	total = 0
	while index >= 0 and arr[index] != 0:
		total += nums[index] * arr[index]
		index -= 1
	print(total)
solve()


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * (n + 1)
	for i in range(q):
		(l, r) = map(int, input().split())
		b[l - 1] += 1
		b[r] -= 1
	for i in range(1, len(b)):
		b[i] += b[i - 1]
	b.pop()
	a.sort()
	b.sort()
	summ = 0
	for (x, y) in zip(a, b):
		summ += x * y
	print(summ)
for _ in range(1):
	solve()


import math, sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
lili = lambda : list(map(int, sys.stdin.readlines()))
li = lambda : list(map(int, input().split()))
I = lambda : int(input())
S = lambda : input().strip()
mod = 1000000007

def initializeDiffArray(A):
	n = len(A)
	D = [0 for i in range(0, n + 1)]
	D[0] = A[0]
	D[n] = 0
	for i in range(1, n):
		D[i] = A[i] - A[i - 1]
	return D

def update(D, l, r, x):
	D[l] += x
	D[r + 1] -= x

def printArray(A, D):
	for i in range(0, len(A)):
		if i == 0:
			A[i] = D[i]
		else:
			A[i] = D[i] + A[i - 1]
(n, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
A = []
for i in range(n):
	A.append(0)
D = initializeDiffArray(A)
for i in range(q):
	(l, r) = list(map(int, input().split()))
	update(D, l - 1, r - 1, 1)
printArray(A, D)
A.sort()
a.sort()
s = 0
for i in range(n):
	s += a[i] * A[i]
print(s)


(n, q) = map(int, input().strip().split(' '))
a = [0]
a[1:] = list(map(int, input().strip().split(' ')))
a.sort()
virtual = [0] * (n + 2)
while q:
	q -= 1
	(x, y) = map(int, input().strip().split())
	virtual[x] += 1
	virtual[y + 1] -= 1
start = 0
built = []
for i in range(0, n + 1):
	start += virtual[i]
	virtual[i] = start
s = 0
virtual.pop()
virtual.sort()
for i in range(n, 0, -1):
	if virtual[i] == 0:
		break
	else:
		s += virtual[i] * a[i]
print(s)


from itertools import accumulate
(_, q) = list(map(int, input().split()))
n = list(map(int, input().split()))
qs = []
rs = [0] * (len(n) + 1)
for _ in range(q):
	(l, r) = list(map(int, input().split()))
	qs.append((l, r))
	rs[l - 1] += 1
	rs[r] -= 1
prs = list(accumulate(rs))[:-1]
d = {}
for (j, i) in zip(sorted(prs), sorted(n)):
	if j in d:
		d[j].append(i)
	else:
		d[j] = [i]
new_arr = [d[x].pop() for x in prs]
new_pres = [0] + list(accumulate(new_arr))
print(sum([new_pres[j] - new_pres[i - 1] for (i, j) in qs]))


import sys
import collections
from collections import Counter
import itertools
import math
import timeit
input = sys.stdin.readline

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	divisors = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				divisors.append(i)
			else:
				divisors.extend([i, n // i])
	return divisors

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def flin(d, x, default=-1):
	left = right = -1
	for i in range(len(d)):
		if d[i] == x:
			if left == -1:
				left = i
			right = i
	if left == -1:
		return (default, default)
	else:
		return (left, right)

def ceil(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)
(n, q) = mi()
d = li()
a = []
for i in range(q):
	(x, y) = mi()
	a.append([x - 1, y - 1])
dif = [0] * n
for i in a:
	dif[i[0]] += 1
	if i[1] != n - 1:
		dif[i[1] + 1] -= 1
for i in range(1, n):
	dif[i] += dif[i - 1]
dic = ddl()
d.sort()
for (pos, el) in enumerate(sorted(dif)):
	dic[el].append(d[pos])
res = 0
for i in range(n):
	res += dif[i] * dic[dif[i]].pop()
print(res)


from sys import stdin, stdout

def update(i, val):
	while i <= n:
		BIT[i] += val
		i = i + (i & -i)

def read(i):
	sm = 0
	while i > 0:
		sm += BIT[i]
		i = i - (i & -i)
	return sm
(n, q) = map(int, stdin.readline().split())
lt = [int(x) for x in stdin.readline().split()]
lt.sort()
BIT = [0] * (n + 1)
for _ in range(q):
	(l, r) = map(int, stdin.readline().split())
	update(l, 1)
	update(r + 1, -1)
nz = [0] * n
for i in range(1, n + 1):
	nz[i - 1] = read(i)
nz.sort()
ans = 0
for i in range(n - 1, -1, -1):
	ans += nz[i] * lt[i]
stdout.write(str(ans))


import sys

def get_ints():
	return map(int, sys.stdin.readline().split())
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
dp = [0] * n
for _ in range(q):
	(s1, e1) = get_ints()
	dp[s1 - 1] += 1
	if e1 != n:
		dp[e1] -= 1
c = 0
for i in range(n):
	c += dp[i]
	dp[i] = c
dp = sorted(dp)
arr = sorted(arr)
summ = 0
for i in range(n):
	summ += dp[i] * arr[i]
print(summ)


import random, math
from copy import deepcopy as dc

def solution():
	pass

def input_test():
	(n, q) = map(int, input().strip().split(' '))
	li = list(map(int, input().strip().split(' ')))
	freq = [0] * n
	for i in range(q):
		(l, r) = map(int, input().strip().split(' '))
		freq[l - 1] += 1
		if r < n:
			freq[r] -= 1
	for i in range(1, n):
		freq[i] = freq[i] + freq[i - 1]
	li.sort()
	freq.sort()
	s = 0
	for i in range(n):
		s += li[i] * freq[i]
	print(s)
input_test()


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
from itertools import permutations
import heapq
I = sys.stdin.readline
alpha = 'abcdefghijklmnopqrstuvwxyz'
mod = 10 ** 9 + 7

def ii():
	return int(I().strip())

def li():
	return list(map(int, I().strip().split()))

def mi():
	return map(int, I().strip().split())

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

def main():
	(n, m) = mi()
	arr = li()
	q = []
	freq = [0] * n
	srt = [0] * n
	end = [0] * n
	for i in range(m):
		(x, y) = mi()
		srt[x - 1] += 1
		end[y - 1] += 1
		q.append((x, y))
	var = 0
	for i in range(n):
		if srt[i] != 0:
			var += srt[i]
		freq[i] = var
		if end[i] != 0:
			var -= end[i]
	freq.sort()
	arr.sort()
	cnt = 0
	for i in range(n - 1, -1, -1):
		cnt += arr[i] * freq[i]
	print(cnt)
main()


from sys import *
input = stdin.buffer.readline
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
d = [0] * (n + 1)
for i in range(m):
	(x, y) = map(int, input().split())
	d[x - 1] += 1
	d[y] -= 1
for i in range(1, n):
	d[i] += d[i - 1]
l.sort(reverse=True)
d.sort(reverse=True)
ka = 0
for i in range(n):
	ka += d[i] * l[i]
print(ka)


from sys import stdin
import math
(n, q) = map(int, stdin.readline().rstrip().split(' '))
nums = list(map(int, stdin.readline().rstrip().split(' ')))
m = max(nums)
qs = []
for _ in range(q):
	(l, r) = map(int, stdin.readline().rstrip().split(' '))
	qs.append((l - 1, r - 1))
freqs = [0] * (n + 1)
for i in range(q):
	(l, r) = qs[i]
	freqs[l] = freqs[l] + 1
	freqs[r + 1] = freqs[r + 1] - 1
for i in range(1, n):
	freqs[i] += freqs[i - 1]
sor = [(i, freq) for (i, freq) in enumerate(freqs[0:n])]
sor.sort(key=lambda x: x[1], reverse=True)
ans = [0] * n
nums.sort(reverse=True)
for i in range(n):
	(ith, _) = sor[i]
	ans[ith] = nums[i]
prefix = [0] * n
prefix[0] = ans[0]
for i in range(1, n):
	prefix[i] = prefix[i - 1] + ans[i]

def prefix_sum(l, r):
	if l == 0:
		return prefix[r]
	return prefix[r] - prefix[l - 1]
s = 0
for (l, r) in qs:
	s += prefix_sum(l, r)
print(s)


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()


(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)


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
(n, q) = mp()
arr = lmp()
ml = l1d(n + 1)
for i in range(q):
	(l, r) = mp()
	ml[l - 1] += 1
	ml[r] -= 1
ml = ml[:-1]
for i in range(1, n):
	ml[i] += ml[i - 1]
ans = 0
ml.sort()
arr.sort()
for i in range(n - 1, -1, -1):
	ans += ml[i] * arr[i]
print(ans)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, q) = value()
a = sorted(array())
status = [0] * (n + 1)
queries = []
for i in range(q):
	(l, r) = value()
	queries.append((l, r))
	status[l - 1] += 1
	status[r] -= 1
count = [status[0]]
for i in range(1, n + 1):
	count.append(count[-1] + status[i])
count = count[:-1]
count = sorted([(count[i], i) for i in range(n)])
ans = [0] * n
i = 0
for (rep, ind) in count:
	ans[ind] = a[i]
	i += 1
a = ans
prefix_array = [0, a[0]]
for i in range(1, n):
	prefix_array.append(prefix_array[-1] + a[i])
ans = 0
for (l, r) in queries:
	ans += prefix_array[r] - prefix_array[l - 1]
print(ans)


(n, q) = map(int, input().split())
ar = list(map(int, input().split()))
fre = [0 for i in range(n)]
while q:
	(l, r) = map(int, input().split())
	fre[l - 1] += 1
	if r != n:
		fre[r] -= 1
	q -= 1
for i in range(1, n):
	fre[i] += fre[i - 1]
print(sum((i * j for (i, j) in zip(sorted(ar), sorted(fre)))))


from io import BytesIO, IOBase
import os
import sys
import pprint
from itertools import *
from collections import *

def solve():
	(n, q) = li()
	arr = li()
	arr = sorted(arr)
	b = [li() for _ in range(q)]
	diff = [0] * (n + 1)
	for i in b:
		(l, r) = i
		diff[l - 1] += 1
		diff[r] -= 1
	diff = sorted(list(accumulate(diff)))[1:]
	ans = 0
	for i in range(n):
		ans += diff[i] * arr[i]
	pr(ans)

def main():
	T = 1
	for _ in range(T):
		solve()
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
main()


from bisect import insort, bisect_right, bisect_left
from sys import stdout, stdin, setrecursionlimit
from heapq import heappush, heappop, heapify
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from math import *
from re import *
from os import *

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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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:
			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')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def getPrimes(N=10 ** 5):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=getPrimes()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
(n, q) = zzz()
arr = szzz()
lst = [0] * n
for i in range(q):
	(l, r) = zzz()
	lst[l - 1] += 1
	try:
		lst[r] -= 1
	except:
		pass
for i in range(1, n):
	lst[i] += lst[i - 1]
lst.sort()
print(sum((arr[i] * lst[i] for i in range(n))))


import sys
from itertools import accumulate
input = lambda : sys.stdin.readline().strip('\r\n')
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
ind = [0] * (n + 1)
for _ in range(q):
	(l, r) = map(int, input().split())
	ind[l - 1] += 1
	ind[r] += -1
count = list(accumulate(ind))[:n]
count.sort()
a.sort()
ans = 0
for i in range(n):
	ans += a[i] * count[i]
print(ans)


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


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
cnt = [0] * n
for _ in range(q):
	(l, r) = map(int, input().split())
	cnt[l - 1] += 1
	if r < n:
		cnt[r] -= 1
st = list()
v = 0
for i in range(n):
	v += cnt[i]
	st.append(v)
st.sort(reverse=True)
sm = 0
for i in range(n):
	sm += a[i] * st[i]
print(sm)


(n, q) = map(int, input().split())
arr = sorted(list(map(int, input().split())))
idxFreq = {}
frequency = [0 for i in range(n + 2)]
for i in range(q):
	(l, r) = map(int, input().split())
	frequency[l] += 1
	frequency[r + 1] -= 1
final = [0]
for i in range(1, n + 2):
	final.append(final[-1] + frequency[i])
final.pop()
final.pop(0)
s = 0
for i in sorted(final, reverse=True):
	s += i * arr.pop()
print(s)


import sys
import math
import operator as op
from functools import reduce

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
t = 1
for i in range(t):
	(n, q) = read_int_line()
	a = read_int_line()
	suf = [0] * (n + 1)
	for i in range(q):
		(l, r) = read_int_line()
		l -= 1
		r -= 1
		suf[l] += 1
		suf[r + 1] -= 1
	for i in range(n):
		suf[i + 1] += suf[i]
	ans = 0
	suf = suf[:n]
	suf.sort()
	a.sort()
	for i in range(n):
		ans += a[i] * suf[i]
	print(ans)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
b = list(map(int, input().split()))
a = [0] * n
for i in range(q):
	(l, r) = map(int, input().split())
	a[l - 1] += 1
	if r < n:
		a[r] -= 1
for i in range(1, n):
	a[i] += a[i - 1]
a.sort(reverse=True)
b.sort(reverse=True)
res = 0
for i in range(n):
	res += a[i] * b[i]
print(res)


from sys import stdin
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
(n, q) = mp()
d = [0] * n
l = sorted(mp(), reverse=True)
for _ in range(q):
	v = mp()
	d[v[0] - 1] += 1
	if v[1] != n:
		d[v[1]] -= 1
for i in range(1, n):
	d[i] += d[i - 1]
d.sort(reverse=True)
ans = 0
for i in range(n):
	ans += d[i] * l[i]
print(ans)


from sys import stdin
input = stdin.readline
(n, q) = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
h = [0] * (n + 2)
ans = 0
while q:
	q -= 1
	(l, r) = map(int, input().split())
	h[l] += 1
	h[r + 1] -= 1
sum = 0
for i in range(len(h)):
	sum += h[i]
	h[i] = sum
sorted_h = sorted(h, reverse=True)
for i in range(len(a)):
	ans += sorted_h[i] * a[i]
print(ans)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
ind = [0] * (n + 1)
ind[0] = 1
qu = []
for i in range(q):
	(l, r) = map(int, input().split())
	qu.append([l - 1, r - 1])
	ind[l - 1] += 1
	ind[r] -= 1
for i in range(1, n):
	ind[i] += ind[i - 1]
x = []
for i in range(n):
	x.append([ind[i], i])
x.sort()
a.sort()
arr = [0] * n
for i in range(n - 1, -1, -1):
	arr[x[i][1]] = a[i]
s = [0] * n
s[0] = arr[0]
for i in range(1, n):
	s[i] = s[i - 1] + arr[i]
ans = 0
for i in range(q):
	(l, r) = qu[i]
	ans = ans + s[r] - s[l] + arr[l]
print(ans)


from functools import reduce
import os
import sys
from collections import *
from math import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def arr():
	return [int(i) for i in input().split()]

def sarr():
	return [int(i) for i in input()]

def starr():
	return [str(x) for x in input().split()]

def inn():
	return int(input())

def svalue():
	return tuple(map(str, input().split()))

def parr():
	return [value() for i in range(n)]
mo = 1000000007
inf = 1e+18
div = 998244353
(n, q) = value()
a = arr()
inc = [0] * (n + 1)
for _ in range(q):
	(x, y) = value()
	inc[x - 1] += 1
	inc[y] -= 1
pre = []
sm = 0
for i in range(n):
	sm += inc[i]
	pre += [sm]
pre.sort(reverse=True)
a.sort(reverse=True)
ans = 0
for i in range(n):
	ans += a[i] * pre[i]
print(ans)


import sys
(n, m) = map(int, sys.stdin.readline().split())
lis = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
s = [0] * n
e = [0] * n
for i in range(m):
	(a, b) = map(int, sys.stdin.readline().split())
	s[a - 1] += 1
	e[b - 1] += 1
store = []
start = 0
end = 0
d = 0
for i in range(n):
	if s[i] and (not e[i]):
		store.append((start - end, d))
		start += s[i]
		d = 1
	elif not s[i] and e[i]:
		d += 1
		store.append((start - end, d))
		end += e[i]
		d = 0
	elif s[i] and e[i]:
		store.append((start - end, d))
		store.append((s[i] + start - end, 1))
		start += s[i]
		end += e[i]
		d = 0
	else:
		d += 1
l = 0
ans = 0
store.sort(reverse=True)
cumm = [0] * n
cumm[0] = lis[0]
for i in range(1, n):
	cumm[i] = cumm[i - 1] + lis[i]
for i in range(len(store) - 1):
	(b, c) = store[i]
	if n > l + c - 1 >= l:
		ans += (cumm[l + c - 1] - cumm[l] + lis[l]) * b
	l += c
print(ans)


from collections import Counter
import string
import math
import sys

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(number_of_variables):
	if number_of_variables == 1:
		return int(sys.stdin.readline())
	if number_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
mod = 1000000007
(n, k) = vary(2)
num = array_int()
tt = [0] * n
for i in range(k):
	(l, r) = vary(2)
	tt[l - 1] += 1
	try:
		tt[r] -= 1
	except:
		pass
for i in range(1, n):
	tt[i] += tt[i - 1]
tt.sort()
num.sort()
ans = 0
for i in range(n):
	ans += tt[i] * num[i]
print(ans)


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


s = input().split()
n = int(s[0])
q = int(s[1])
a = input().split()
my_dict = [0 for i in range(n)]
for i in range(q):
	r = input().split()
	my_dict[int(r[0]) - 1] += 1
	if int(r[1]) < n:
		my_dict[int(r[1])] -= 1
my_dict_upd = [0 for i in range(n)]
v = 0
for i in range(n):
	v += my_dict[i]
	my_dict_upd[i] = v
my_dict_upd.sort(reverse=True)
s = 0
b = [0 for i in range(n)]
for i in range(n):
	b[i] = int(a[i])
b.sort(reverse=True)
for i in range(n):
	if my_dict_upd[i] == 0:
		break
	else:
		s += my_dict_upd[i] * b[i]
print(s)


from heapq import *

def frequent(n, q):
	A = [0 for i in range(0, n)]
	D = [0 for i in range(0, n + 1)]
	for i in q:
		D[i[0] - 1] += 1
		D[i[1]] -= 1
	for i in range(0, len(A)):
		if i == 0:
			A[i] = D[i]
		else:
			A[i] = D[i] + A[i - 1]
	return A

def answer(A, B):
	a = 0
	A.sort()
	B.sort()
	for i in range(0, len(A)):
		a += A[i] * B[i]
	return a
(n, p) = map(int, input().split())
A = list(map(int, input().split()))
q = []
for i in range(0, p):
	q.append(list(map(int, input().split())))
B = frequent(n, q)
ans = answer(B, A)
print(ans)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = [int(x) for x in input().split()]
b = [0] * n
d = [0] * (n + 1)
for i in range(q):
	(l, r) = map(int, input().split())
	d[l - 1] += 1
	d[r] -= 1
k = 0
for i in range(n):
	k += d[i]
	b[i] = k
b.sort()
a.sort()
ans = 0
for i in range(n):
	ans += a[i] * b[i]
print(ans)


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def solve():
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	sfx = [0] * (n + 2)
	for _ in range(q):
		(l, r) = map(int, input().split())
		sfx[l] += 1
		sfx[r + 1] -= 1
	for i in range(1, len(sfx)):
		sfx[i] += sfx[i - 1]
	sfx.sort(reverse=True)
	res = 0
	idx = 0
	while idx < len(sfx) and sfx[idx] > 0:
		res += sfx[idx] * arr[idx]
		idx += 1
	cout << res << endl

def main():
	solve()
main()


def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP2():
	return map(float, input().split())

def LIST():
	return list(map(int, input().split()))

def STRING():
	return input()
import string
import sys
from heapq import heappop, heappush
from bisect import *
from collections import deque, Counter
from math import *
from itertools import permutations, accumulate
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
(n, q) = MAP()
arr = LIST()
x = [0] * (n + 2)
for i in range(q):
	(l, r) = MAP()
	x[l] += 1
	x[r + 1] -= 1
for i in range(2, n + 2):
	x[i] += x[i - 1]
x.sort(reverse=True)
arr.sort(reverse=True)
sm = 0
for i in range(n):
	sm += x[i] * arr[i]
print(sm)


(n, q) = map(int, input().split())
numbers_list = list(map(int, input().split()))
list_val = [0] * n
for i in range(q):
	(l, u) = map(int, input().split())
	list_val[l - 1] += 1
	if u <= n - 1:
		list_val[u] -= 1
for i in range(1, n):
	list_val[i] += list_val[i - 1]
numbers_list.sort()
list_val.sort()
max_sum = 0
for m in range(n):
	max_sum += numbers_list[m] * list_val[m]
print(max_sum)


(n, q) = map(int, input().split())
nums = list(map(int, input().split()))
nums = sorted(nums)
acum = [0] * len(nums)
for i in range(q):
	(l, r) = map(int, input().split())
	l = l - 1
	r = r - 1
	acum[l] += 1
	if r < n - 1:
		acum[r + 1] -= 1
for i in range(n)[1:]:
	acum[i] = acum[i - 1] + acum[i]
acum = sorted(acum)
s = 0
for i in range(n):
	s += acum[i] * nums[i]
print(s)


import os
import sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

def array():
	return list(map(int, sys.stdin.readline().split()))

def intt():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(input())
from itertools import permutations as pmt
from collections import Counter
from collections import deque
(n, q) = intt()
arr = array()
ans = [0] * n
arr.sort()
for i in range(q):
	(u, v) = intt()
	ans[u - 1] += 1
	if v <= n - 1:
		ans[v] -= 1
anss = 0
for i in range(n):
	if i > 0:
		ans[i] = ans[i] + ans[i - 1]
	else:
		ans[i] = ans[0]
ans.sort()
for i in range(n):
	anss += arr[i] * ans[i]
print(anss)


(n, q) = list(map(int, input().split(' ')))
nums = list(map(int, input().split(' ')))
q_tokens = [0 for i in range(n + 2)]
for i in range(q):
	(a, b) = list(map(int, input().split(' ')))
	q_tokens[a] += 1
	q_tokens[b + 1] -= 1
times_called = [0 for i in range(n)]
suma = 0
for i in range(n):
	suma += q_tokens[i + 1]
	times_called[i] = suma
sorted_indexes = sorted([x for x in range(n)], key=lambda y: times_called[y], reverse=1)
nums = sorted(nums, reverse=1)
total_sum = 0
for i in range(n):
	total_sum += nums[i] * times_called[sorted_indexes[i]]
print(total_sum)


(n, q) = map(int, input().split())
a = [int(x) for x in input().split()]
p = [0] * (n + 1)
for _ in range(q):
	(l, r) = map(int, input().split())
	p[l - 1] += 1
	p[r] -= 1
s = [p[0]]
for i in range(1, n):
	s.append(s[-1] + p[i])
s.sort()
a.sort()
ans = 0
for i in range(n):
	ans += a[i] * s[i]
print(ans)


input = __import__('sys').stdin.readline
(n, m) = map(int, input().split())
lis = sorted(map(int, input().split()), reverse=True)
ans = [0] * (n + 2)
for i in range(m):
	(a, b) = map(int, input().split())
	ans[a] += 1
	ans[b + 1] -= 1
for i in range(1, n + 1):
	ans[i] += ans[i - 1]
ans.sort(reverse=True)
fin = 0
for i in range(n):
	fin += lis[i] * ans[i]
print(fin)


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
freq = [0] * (n + 2)
for _ in range(q):
	(x, y) = map(int, input().split())
	freq[x] = freq[x] + 1
	freq[y + 1] = freq[y + 1] - 1
freq = freq[1:n + 1]
for i in range(1, n):
	freq[i] = freq[i] + freq[i - 1]
freq.sort(reverse=True)
sum = 0
for j in range(n):
	sum = sum + freq[j] * arr[j]
print(sum)


(n, q) = list(map(int, input().split()))
arr = list(map(int, input().split()))
diff = [0 for i in range(n)]
for i in range(q):
	(u, v) = list(map(int, input().split()))
	u -= 1
	diff[u] += 1
	if v < n:
		diff[v] -= 1
for i in range(1, n):
	diff[i] += diff[i - 1]
arr.sort()
diff.sort()
ans = 0
for i in range(n):
	ans += diff[i] * arr[i]
print(ans)


(n, q) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
freq = [0] * (n + 1)
for _ in range(q):
	(l, r) = [int(i) for i in input().split()]
	freq[l - 1] += 1
	freq[r] -= 1
for i in range(1, n):
	freq[i] += freq[i - 1]
freq.pop(-1)
arr.sort()
freq.sort()
ans = 0
for i in range(n):
	ans += arr[i] * freq[i]
print(ans)


(n, q) = map(int, input().split())
a = input().split()
for i in range(n):
	a[i] = int(a[i])
b = [0 for i in range(n)]
for i in range(q):
	(l, r) = map(int, input().split())
	b[l - 1] += 1
	if r != n:
		b[r] -= 1
c = []
sum = 0
for i in range(len(b)):
	sum += b[i]
	c.append(sum)
c.sort()
a.sort()
ans = 0
for i in range(n):
	ans += a[i] * c[i]
print(ans)


from bisect import bisect_left
import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict
from collections import deque
from functools import cmp_to_key
import math
import heapq
import re

def sin():
	return input()

def ain():
	return list(map(int, sin().split()))

def sain():
	return input().split()

def iin():
	return int(sin())
MAX = float('inf')
MIN = float('-inf')
MOD = 1000000007

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	s = set()
	for p in range(2, n + 1):
		if prime[p]:
			s.add(p)
	return s

def readTree(n, m):
	adj = [deque([]) for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = ain()
		adj[u].append(v)
		adj[v].append(u)
	return adj

def main():
	(n, q) = ain()
	a = ain()
	a.sort(reverse=True)
	suma = 0
	p = [0] * (n + 1)
	for _ in range(q):
		(l, r) = ain()
		p[l - 1] += 1
		p[r] -= 1
	d = deque([])
	x = -1
	for i in range(n):
		if d == deque([]):
			d.append(p[i])
			x = p[i]
		elif p[i] >= 0:
			x += p[i]
			d.append(x)
		else:
			x += p[i]
			d.append(x)
	d = sorted(d, reverse=True)
	for i in range(n):
		suma += d[i] * a[i]
	print(suma)
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')
if os.getcwd() == 'D:\\code':
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def seive(n):
	primes = [True] * (n + 1)
	ans = []
	for i in range(2, n):
		if not primes[i]:
			continue
		j = 2 * i
		while j <= n:
			primes[j] = False
			j += i
	for p in range(2, n + 1):
		if primes[p]:
			ans += [p]
	return ans

def factors(n):
	factors = []
	x = 2
	while x * x <= n:
		while n % x == 0:
			factors.append(x)
			n //= x
		if n > 1:
			factors.append(x)
	return factors

def update(x, val):
	while x <= n:
		tree[x] += val
		x += x & -x

def read(x):
	s = 0
	while x > 0:
		s += tree[x]
		x -= x & -x
	return s
niz = [0] * 300001
tree = [0] * 300001
(n, q) = (0, 0)

def main():
	try:
		(n, q) = invr()
		a = inlt()
		ind = [0] * (n + 1)
		while q:
			q -= 1
			(l, r) = invr()
			ind[l - 1] += 1
			ind[r] -= 1
		for i in range(1, n):
			ind[i] += ind[i - 1]
		a.sort(reverse=1)
		ind.sort(reverse=1)
		ans = 0
		for i in range(n):
			ans += ind[i] * a[i]
		print(ans)
	except Exception as e:
		print(e)
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def incrementByD(arr, q_arr, n, m, d):
	sum = [0 for i in range(n)]
	for i in range(m):
		sum[q_arr[i][0]] += d
		if q_arr[i][1] + 1 < n:
			sum[q_arr[i][1] + 1] -= d
	arr[0] += sum[0]
	for i in range(1, n):
		sum[i] += sum[i - 1]
		arr[i] += sum[i]
	arr.pop(0)
	return arr
(n, q) = map(int, input().split())
aa = list(map(int, input().split()))
q_arr = []
for i in range(q):
	(l, r) = map(int, input().split())
	q_arr.append([l, r])
arr = [0] * (n + 1)
d = 1
m = incrementByD(arr, q_arr, n + 1, q, d)
aa.sort()
m.sort()
ans = 0
for i in range(n):
	ans += aa[i] * m[i]
print(ans)


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))


(n, q) = list(map(int, input().split()))
arr = list(map(int, input().split()))
arr2 = [0] * n
for _ in range(q):
	(a, b) = list(map(int, input().split()))
	arr2[a - 1] += 1
	if b <= n - 1:
		arr2[b] -= 1
for i in range(1, n):
	arr2[i] += arr2[i - 1]
arr.sort()
arr2.sort()
ans = 0
for i in range(n):
	ans += arr[i] * arr2[i]
print(ans)


(n, q) = map(int, input().split())
a = [int(x) for x in input().split()]
s = [0] * n
for _ in range(q):
	(l, r) = map(int, input().split())
	s[l - 1] += 1
	if r != n:
		s[r] -= 1
cnt = 0
for i in range(n):
	cnt += s[i]
	s[i] = cnt
s.sort()
a.sort()
print(sum((x * y for (x, y) in zip(s, a))))


from operator import itemgetter
from sys import stdin, stdout
(n, q) = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
arr.sort(reverse=True)
freq_arr = [0] * n
query = []
for i in range(q):
	(l, r) = map(int, stdin.readline().split())
	temp = []
	temp.append(l)
	temp.append(r)
	query.append(temp)
	freq_arr[l - 1] += 1
	if r < n:
		freq_arr[r] -= 1
pre_fix_sum = [0] * n
pre_fix_sum[0] = freq_arr[0]
for i in range(1, n):
	pre_fix_sum[i] = pre_fix_sum[i - 1] + freq_arr[i]
pre_fix_sum = list(enumerate(pre_fix_sum, 0))
pre_fix_sum.sort(key=itemgetter(1), reverse=True)
result = [0] * n
for i in range(n):
	result[pre_fix_sum[i][0]] = arr[i]
req_sum = 0
pre_fix_sum_final = [0] * n
pre_fix_sum_final[0] = result[0]
for i in range(1, n):
	pre_fix_sum_final[i] = pre_fix_sum_final[i - 1] + result[i]
for i in query:
	if i[0] == 1:
		req_sum += pre_fix_sum_final[i[1] - 1]
	else:
		req_sum += pre_fix_sum_final[i[1] - 1] - pre_fix_sum_final[i[0] - 2]
stdout.write(str(req_sum) + '\n')


import sys
input = sys.stdin.buffer.readline

def prog():
	(n, q) = map(int, input().split())
	array = list(map(int, input().split()))
	array.sort()
	starts = [0 for i in range(n + 1)]
	stops = [0 for i in range(n + 1)]
	for i in range(q):
		(start, stop) = map(int, input().split())
		starts[start] += 1
		stops[stop] += 1
	appearances = [starts[1]]
	for i in range(2, n + 1):
		appearances.append(appearances[-1] + starts[i] - stops[i - 1])
	appearances.sort()
	total_sum = 0
	for i in range(n):
		total_sum += appearances[i] * array[i]
	print(total_sum)
prog()


(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)


(n, q) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
s = [0 for i in range(n)]
for i in range(q):
	(l, r) = [int(j) for j in input().split()]
	s[l - 1] += 1
	if r < n:
		s[r] -= 1
r = 0
for i in range(n):
	r += s[i]
	s[i] = r
a.sort()
s.sort()
r = 0
for i in range(n):
	r += a[i] * s[i]
print(r)


(n, q) = input().split()
n = int(n)
q = int(q)
a = [int(x) for x in input().split()]
freq = [0 for x in a]
for i in range(q):
	ranges = [int(x) for x in input().split()]
	freq[ranges[0] - 1] += 1
	if ranges[1] < n:
		freq[ranges[1]] -= 1
for i in range(1, n):
	freq[i] += freq[i - 1]
a.sort()
freq.sort()
sum = 0
for i in range(len(freq)):
	sum += a[i] * freq[i]
print(sum)


from sys import stdin, stdout
import math
input = stdin.readline

def print(x):
	stdout.write(str(x) + '\n')
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
pref = [0] * (n + 1)
for i in range(q):
	(u, v) = map(int, input().split())
	u -= 1
	pref[u] += 1
	pref[v] -= 1
for i in range(1, n):
	pref[i] += pref[i - 1]
pref.sort()
l.sort()
ans = 0
pref.pop(0)
for i in range(n):
	ans += pref[i] * l[i]
print(ans)


(n, q) = map(int, input().split())
l = list(map(int, input().split()))
arr = [0] * n
for i in range(q):
	(a, b) = map(int, input().split())
	arr[a - 1] += 1
	if b < n:
		arr[b] -= 1
val = 0
for i in range(n):
	val = val + arr[i]
	arr[i] = val
arr.sort()
l.sort()
ans = 0
for i in range(n):
	ans += arr[i] * l[i]
print(ans)


import sys
import math as mt
input = sys.stdin.buffer.readline
t = 1
for __ in range(t):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	d = [0] * (n + 1)
	for _ in range(q):
		(li, ri) = map(int, input().split())
		d[li - 1] += 1
		d[ri] -= 1
	for i in range(1, n + 1):
		d[i] += d[i - 1]
	l.sort(reverse=True)
	ind = 0
	d.sort(reverse=True)
	ans = 0
	for i in range(n):
		ans += d[i] * l[i]
	print(ans)


import sys
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def update(index, value, array, bi_tree):
	while index < len(array):
		bi_tree[index] += value
		index += index & -index

def get_sum(index, bi_tree):
	ans = 0
	while index > 0:
		ans += bi_tree[index]
		index -= index & -index
	return ans

def get_range_sum(left, right, bi_tree):
	ans = get_sum(right, bi_tree) - get_sum(left - 1, bi_tree)
	return ans

def g(x):
	return x

def solve():
	(N, Q) = getInts()
	A = getInts()
	A.sort()
	A = [0] + A
	queries = []
	res = 0
	B = [0] * (N + 1)
	f = [0 for n in range(N + 1)]
	for q in range(Q):
		(L, R) = getInts()
		update(L, 1, B, f)
		update(R + 1, -1, B, f)
	for i in range(1, N + 1):
		B[i] = get_sum(i, f)
	B = B[1:]
	B.sort()
	B = [0] + B
	ans = 0
	for j in range(1, N + 1):
		ans += A[j] * B[j]
	return ans
ans = solve()
print(ans)


from math import *
from collections import *
from random import *
from bisect import *
import sys
input = sys.stdin.readline

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())

def inp():
	return int(input())
(n, q) = ma()
a = lis()
d = [[0, i] for i in range(n)]
for i in range(q):
	(x, y) = ma()
	d[x - 1][0] += 1
	if y != n:
		d[y][0] -= 1
for i in range(1, n):
	d[i][0] += d[i - 1][0]
d.sort(reverse=True)
a.sort(reverse=True)
r = 0
po = 0
for i in d:
	r += i[0] * a[po]
	po += 1
print(r)


def main():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	lr_list = [0] * n
	for i in range(q):
		(l, r) = map(int, input().split())
		(l, r) = (l - 1, r - 1)
		lr_list[l] += 1
		if r < n - 1:
			lr_list[r + 1] -= 1
	lr_cumul = 0
	freq = []
	for i in lr_list:
		lr_cumul += i
		freq.append(lr_cumul)
	freq.sort(reverse=True)
	a.sort(reverse=True)
	output = sum([a[i] * freq[i] for i in range(len(freq))])
	print(output)
main()


from heapq import heapify, heappop
(number_of_elements, number_of_query) = map(int, input().strip().split())
array = list(map(int, input().strip().split()))
frequency_array = [0] * (number_of_elements + 1)
for query in range(number_of_query):
	(start_index, end_index) = map(int, input().strip().split())
	frequency_array[start_index - 1] += 1
	frequency_array[end_index] -= 1
value = 0
for position in range(number_of_elements + 1):
	frequency_array[position] = frequency_array[position] + value
	value = frequency_array[position]
frequency_array.pop()
heapify(frequency_array)
heapify(array)
maximum_sum = 0
while number_of_elements > 0:
	number_of_elements -= 1
	maximum_sum += heappop(frequency_array) * heappop(array)
print(maximum_sum)


import itertools
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
b = list(sorted(map(int, input().split())))
a = [0] * (n + 1)
for _ in range(q):
	(l, r) = map(int, input().split())
	a[l - 1] += 1
	a[r] -= 1
a = list(sorted(itertools.accumulate(a)))
print(sum((a[i + 1] * b[i] for i in range(n))))


import sys
input = sys.stdin.buffer.readline

def solution():
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	ql = [0] * (n + 1)
	qa = []
	for i in range(q):
		(x, y) = map(int, input().split())
		qa.append((x, y))
		ql[x - 1] += 1
		ql[y] -= 1
	for i in range(1, len(ql)):
		ql[i] += ql[i - 1]
	ql.sort(reverse=True)
	l.sort(reverse=True)
	s = 0
	for i in range(n):
		s += l[i] * ql[i]
	print(s)
solution()


import sys
from math import sqrt
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(n, q) = map(int, input().split())
nums = list(map(int, input().split()))
nums = sorted(nums, reverse=True)
cntStartFromIdx = [0] * (n + 1)
cntEndFromIdx = [0] * (n + 1)
cnts = [0] * n
for i in range(q):
	(start, end) = map(int, input().split())
	cntStartFromIdx[start] += 1
	if end + 1 <= n:
		cntEndFromIdx[end + 1] += 1
accumSum = 0
for i in range(1, n + 1):
	accumSum += cntStartFromIdx[i] - cntEndFromIdx[i]
	cnts[i - 1] = accumSum
cnts = sorted(cnts, reverse=True)
res = 0
for i in range(n):
	res += nums[i] * cnts[i]
print(res)


from sys import *

def input():
	return stdin.readline()[:-1]

def initailze(a):
	n = len(a)
	d = [0] * (n + 1)
	d[0] = a[0]
	d[n] = 0
	for i in range(1, n):
		d[i] = a[i] - a[i - 1]
	return d

def update(d, l, r, x):
	d[l] += x
	d[r + 1] -= x

def printarray(a, d):
	l = []
	for i in range(0, len(a)):
		if i == 0:
			a[i] = d[i]
		else:
			a[i] = d[i] + a[i - 1]
		l.append(a[i])
	return l
(n, q) = map(int, input().split())
orig = [int(i) for i in input().split()]
a = [0] * n
d = initailze(a)
sm = 0
for _ in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	update(d, x, y, 1)
fin = printarray(a, d)
orig.sort(reverse=True)
fin.sort(reverse=True)
for i in range(n):
	sm += fin[i] * orig[i]
print(sm)


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
(n, q) = ilele()
A = alele()
B = []
dp = [0] * (n + 1)
for i in range(q):
	(a, b) = ilele()
	a -= 1
	b -= 1
	dp[a] += 1
	dp[b + 1] -= 1
dp = list(accumulate(dp))
dp.pop()
dp.sort()
A.sort()
ans = 0
while A and dp:
	ans += A.pop() * dp.pop()
print(ans)


(n, m) = map(int, input().split())
lis = sorted(map(int, input().split()), reverse=True)
ans = [0] * (200000 + 2)
ans1 = [0] * (200000 + 2)
ans2 = [0] * (200000 + 2)
for i in range(m):
	(a, b) = map(int, input().split())
	ans[a] += 1
	ans1[b] += 1
for i in range(1, 200000 + 2):
	ans2[i] = ans[i] - ans1[i - 1] + ans2[i - 1]
ans2.sort(reverse=True)
kk = 0
for i in range(n):
	kk += ans2[i] * lis[i]
print(kk)


import sys
input = sys.stdin.buffer.readline

def solution():
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	ql = [0] * (n + 1)
	qa = []
	for i in range(q):
		(x, y) = map(int, input().split())
		qa.append((x, y))
		ql[x - 1] += 1
		ql[y] -= 1
	for i in range(1, len(ql)):
		ql[i] += ql[i - 1]
	a = []
	for i in range(len(ql)):
		a.append((ql[i], -i))
	ans = [0] * n
	a.sort(reverse=True)
	l.sort(reverse=True)
	for i in range(n):
		ind = abs(a[i][1])
		val = l[i]
		ans[ind] = val
	ans.reverse()
	ans.append(0)
	ans.reverse()
	for i in range(1, n + 1):
		ans[i] += ans[i - 1]
	s = 0
	for i in range(q):
		l = qa[i][0] - 1
		r = qa[i][1]
		s += ans[r] - ans[l]
	print(s)
solution()


(a, b) = map(int, input().split())
k = sorted(map(int, input().split()))
t = [0 for i in range(a + 1)]
for _ in range(b):
	(st, en) = map(int, input().split())
	t[st - 1] += 1
	t[en] -= 1
v = []
ans = out = 0
for i in range(a + 1):
	ans += t[i]
	v.append(ans)
v.sort()
for i in range(a):
	if v[-1] == 0 or k[-1] == 0:
		break
	out += k.pop() * v.pop()
print(out)


(n, q) = map(int, input().split())
l = list(map(int, input().split()))
p = []
a = [0] * (n + 2)
for i in range(q):
	(x, y) = map(int, input().split())
	p.append([x, y])
	a[x] += 1
	a[y + 1] -= 1
for i in range(1, n + 1):
	a[i] += a[i - 1]
a = a[0:n + 1]
for i in range(len(a)):
	a[i] = [a[i], i]
a.sort()
l.sort()
a = a[::-1]
l = l[::-1]
l.append(0)
ans = 0
for i in range(len(a)):
	ans += a[i][0] * l[i]
print(ans)


from sys import stdin, stdout
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial, log2, floor
from bisect import bisect_right as br, bisect_left as bl
import heapq
(n, k) = mp()
l = sorted(mp(), reverse=True)
v = [0] * n
for _ in range(k):
	(a, b) = mp()
	v[a - 1] += 1
	if b != n:
		v[b] -= 1
for i in range(1, n):
	v[i] += v[i - 1]
v.sort(reverse=True)
ans = 0
for i in range(n):
	ans += v[i] * l[i]
print(ans)


import time, math, bisect, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IO():
	return stdin.readline()

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def readTree():
	v = int(input())
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def solve():
	(n, q) = IP()
	lo = L()
	li = []
	(l, r) = (n + 1, -1)
	for i in range(q):
		(ll, rr) = IP()
		if ll - 1 < l:
			l = ll - 1
		if rr - 1 > r:
			r = rr - 1
		li.append([ll - 1, rr - 1])
	cnt = [0] * (n + 1)
	for ele in li:
		cnt[ele[0]] = cnt[ele[0]] + 1
		cnt[ele[1] + 1] = cnt[ele[1] + 1] - 1
	for i in range(1, len(cnt)):
		cnt[i] = cnt[i] + cnt[i - 1]
	cnt.pop()
	cnt.sort()
	lo.sort()
	sm = 0
	for i in range(len(cnt)):
		sm += lo[i] * cnt[i]
	print(sm)
solve()


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
qus = []
for _ in range(q):
	(l, r) = map(int, input().split())
	qus.append((l, r))
starts = [0] * (n + 1)
for (l, r) in qus:
	starts[l - 1] += 1
	starts[r] -= 1
counts = [0] * n
active = 0
for i in range(n):
	active += starts[i]
	counts[i] = active
counts.sort()
arr.sort()
print(sum((val * count for (val, count) in zip(arr, counts))))


from sys import stdin, stdout
input = stdin.readline
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
l1 = [0] * (n + 2)
for i in range(q):
	(left, right) = map(int, input().split())
	l1[left] += 1
	l1[right + 1] -= 1
for i in range(1, n + 1):
	l1[i] += l1[i - 1]
t = l1[1:n + 1].copy()
t.sort(reverse=True)
l.sort(reverse=True)
ans = 0
for i in range(n):
	if t[i] > 0:
		ans += t[i] * l[i]
print(ans)


from itertools import accumulate
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
arr = [0 for _ in range(n)]
for _ in range(q):
	(l, r) = map(int, input().split())
	arr[l - 1] += 1
	if r < n:
		arr[r] -= 1
arr = list(accumulate(arr))
arr.sort()
ans = 0
for i in range(n):
	ans += a[i] * arr[i]
print(ans)


from sys import stdin, stdout

def INI():
	return int(stdin.readline())

def INL():
	return [int(_) for _ in stdin.readline().split()]

def INS():
	return stdin.readline()

def MOD():
	return pow(10, 9) + 7

def OPS(ans):
	stdout.write(str(ans) + '\n')

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')
(n, q) = INL()
X = sorted(INL(), reverse=True)
ans = 0
D = {i: 0 for i in range(n)}
for _ in range(q):
	(l, r) = INL()
	D[l - 1] += 1
	if r < n:
		D[r] -= 1
for _ in range(1, n):
	D[_] += D[_ - 1]
D = {k: v for (k, v) in sorted(D.items(), reverse=True, key=lambda item: item[1])}
i = 0
for _ in D:
	ans += D[_] * X[i]
	i += 1
OPS(ans)


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
suf = [0 for i in range(n + 2)]
while q:
	(l, r) = map(int, input().split())
	suf[l] += 1
	suf[r + 1] -= 1
	q -= 1
for i in range(1, n + 2):
	suf[i] += suf[i - 1]
suf.sort(reverse=True)
ans = 0
for i in range(n):
	ans += suf[i] * arr[i]
print(ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
from heapq import *
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, q) = mp()
	l = li()
	cur = [0] * (n + 1)
	x = []
	for i in range(q):
		(a, b) = mp()
		cur[a] += 1
		if b + 1 <= n:
			cur[b + 1] -= 1
		x.append((a, b))
	h1 = sorted(l)
	for i in range(1, n + 1):
		cur[i] += cur[i - 1]
	cur.sort()
	ans = 0
	while h1:
		ele = h1.pop()
		no = cur.pop()
		ans += no * ele
	pr(ans)
for _ in range(1):
	solve()


import sys
stdin = sys.stdin
stdout = sys.stdout

def getCount(intervals, n):
	counts = [0 for i in range(n)]
	val = [0 for i in range(n + 1)]
	for (i, j) in intervals:
		val[i] += 1
		val[j + 1] -= 1
	currentVal = 0
	for (i, num) in enumerate(val[:-1]):
		currentVal += num
		counts[i] = currentVal
	return counts
(n, q) = [int(_) for _ in stdin.readline().split()]
arr = [int(_) for _ in stdin.readline().strip().split()]
intervals = [[int(_) - 1 for _ in stdin.readline().strip().split()] for i in range(q)]
counts = getCount(intervals, n)
counts.sort()
arr.sort()
ans = 0
for i in range(n):
	ans += arr[i] * counts[i]
stdout.write(f'{ans}\n')


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


(n, q) = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
de = {i: 0 for i in range(n)}
for _ in range(q):
	(a1, b) = [int(i) for i in input().split()]
	de[a1 - 1] += 1
	if b < n:
		de[b] -= 1
for _ in range(1, n):
	de[_] += de[_ - 1]
de = {k: v for (k, v) in sorted(de.items(), key=lambda item: item[1], reverse=True)}
a.sort(reverse=True)
t = 0
su = 0
for i in de.keys():
	if de[i] == 0:
		break
	su += a[t] * de[i]
	t += 1
print(su)


from io import BytesIO, IOBase
import sys, os
inpl = lambda : list(map(int, input().split()))
inpm = lambda : map(int, input().split())
inpi = lambda : int(input())
inp = lambda : input()
(rev, ra, l) = (reversed, range, len)
P = print
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left as bl
from bisect import bisect_right as br
import sys, operator, math, operator
from collections import Counter
import random
(n, q) = inpm()
li = inpl()
li1 = []
for i in ra(q):
	li1.append(inpl())
pref = [0] * (n + 1)
for i in ra(q):
	(a, b) = li1[i]
	pref[a] += 1
	if b + 1 <= n:
		pref[b + 1] -= 1
pre = [pref[0]]
for i in ra(1, l(pref)):
	pre.append(pre[-1] + pref[i])
pre.sort(reverse=True)
ans = 0
li.sort(reverse=True)
for i in ra(n):
	ans += pre[i] * li[i]
P(ans)


(n, q) = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
A.sort()
M = [0] * n
for i in range(q):
	(l, r) = map(int, input().strip().split())
	l = l - 1
	M[l] = M[l] + 1
	if r < n:
		M[r] = M[r] - 1
for i in range(1, n):
	M[i] = M[i - 1] + M[i]
M.sort()
s = 0
for i in range(n):
	s += M[i] * A[i]
print(s)


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)


from sys import stdin, stdout
(n, m) = map(int, input().split())
l = [0] * n
s = list(map(int, input().split()))
for _ in range(m):
	j = stdin.readline()
	(j, k) = map(int, j.split())
	l[j - 1] += 1
	if k < n:
		l[k] -= 1
for i in range(1, n):
	l[i] += l[i - 1]
l.sort()
s.sort()
for i in range(n):
	l[i] = l[i] * s[i]
print(sum(l))


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
qs = [0 for a in arr]
for i in range(q):
	(qa, qb) = map(int, input().split())
	qs[qa - 1] += 1
	if qb < n:
		qs[qb] -= 1
current_val = 0
for i in range(n):
	current_val += qs[i]
	qs[i] = current_val
arr.sort()
nums = sorted(qs)
total = 0
for (n, a) in zip(arr, nums):
	total += n * a
print(total)


(n, q) = map(int, input().split())
L = list(map(int, input().split()))
l1 = [0] * n
s = 0
while q:
	(l, r) = map(int, input().split())
	l1[l - 1] = l1[l - 1] + 1
	if r < n:
		l1[r] = l1[r] - 1
	q = q - 1
for i in range(1, n):
	l1[i] = l1[i - 1] + l1[i]
L.sort()
l1.sort()
for i in range(0, n):
	s += L[i] * l1[i]
print(s)


(n, q) = map(int, input().split())
l1 = list(map(int, input().split()))
l2 = [0] * (n + 1)
for i in range(0, q):
	(l, r) = map(int, input().split())
	l2[l - 1] += 1
	l2[r] -= 1
l3 = []
for i in range(0, n + 1):
	if i == 0:
		l3.append(l2[0])
	else:
		l3.append(l3[i - 1] + l2[i])
l3.sort()
l3 = l3[::-1]
l1.sort()
l1 = l1[::-1]
ans = 0
for i in range(0, n):
	if l3[i] == 0:
		break
	ans += l1[i] * l3[i]
print(ans)


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


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


def read():
	return [int(c) for c in input().split()]

def solve(n, q, array, queries):
	cum = [0] * (n + 1)
	for (a, b) in queries:
		cum[a - 1] += 1
		cum[b] -= 1
	acc = []
	for (i, e) in enumerate(cum):
		acc.append(e if i == 0 else acc[-1] + e)
	return sum((i * j for (i, j) in zip(sorted(acc[:-1]), sorted(array))))

def main():
	(n, q) = read()
	array = read()
	queries = [read() for _ in range(q)]
	ans = solve(n, q, array, queries)
	print(ans)
main()


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict
import math
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
d = [0] * n
for i in range(k):
	(x, y) = map(int, input().split(' '))
	d[x - 1] += 1
	if y < n:
		d[y] -= 1
to_add = d[0]
for i in range(1, n):
	now = d[i]
	d[i] += to_add
	to_add += now
d.sort(reverse=True)
l.sort(reverse=True)
ans = 0
for i in range(n):
	ans += d[i] * l[i]
print(ans)


import sys
(n, k) = map(int, input().split())
p = [0] * (n + 1)
d = sorted(list(map(int, input().split())), reverse=True)
for i in range(k):
	(l, r) = map(int, input().split())
	l -= 1
	p[l] += 1
	p[r] -= 1
for j in range(len(p) - 1):
	p[j + 1] += p[j]
p = sorted(p, reverse=True)
s = 0
for i in range(len(p) - 1):
	s += p[i] * d[i]
print(s)


class BIT:

	def __init__(self, l):
		self._freq = [0] * l

	def add_region(self, l, r):
		self._freq[l] += 1
		try:
			self._freq[r + 1] -= 1
		except IndexError:
			pass

	def get_freq(self):
		ans = []
		cur_sum = 0
		for i in range(len(self._freq)):
			cur_sum += self._freq[i]
			ans.append(cur_sum)
		return ans
(n, q) = map(int, input().split())
iniarr = [int(x) for x in input().split()]
freq = BIT(n)
for i in range(q):
	(l, r) = map(int, input().split())
	freq.add_region(l - 1, r - 1)
ansfreq = sorted(freq.get_freq(), reverse=True)
iniarr.sort(reverse=True)
ans = 0
for i in range(n):
	ans += ansfreq[i] * iniarr[i]
print(ans)


from collections import Counter, defaultdict, deque
import heapq as hq
(n, q) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
c = [0] * (n + 1)
for i in range(q):
	(l, r) = [int(x) - 1 for x in input().split()]
	c[l] += 1
	c[r + 1] -= 1
for i in range(len(c) - 1):
	c[i + 1] += c[i]
c.pop()
c.sort()
arr.sort()
total = 0
for i in range(n):
	total += c[i] * arr[i]
print(total)


from sys import stdin
_input = stdin.readline
(_int, _range) = (int, range)

def solution():
	(n, query_count) = [_int(i) for i in _input().split()]
	arr = [_int(i) for i in _input().split()]
	query = [0] * n
	for i in _range(query_count):
		(l, r) = [_int(i) for i in _input().split()]
		l -= 1
		r -= 1
		query[l] += 1
		if r + 1 < n:
			query[r + 1] -= 1
	ans = [0] * n
	ans[0] = query[0]
	for i in _range(1, n):
		ans[i] = ans[i - 1] + query[i]
	ans.sort(reverse=True)
	arr.sort(reverse=True)
	accum = 0
	for i in _range(n):
		accum += ans[i] * arr[i]
	print(accum)
solution()


from itertools import accumulate
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
pf = [0] * n
for _ in range(q):
	(l, r) = map(int, input().split())
	pf[l - 1] += 1
	if r != n:
		pf[r] -= 1
prf = list(accumulate(pf))
prf.sort(reverse=True)
ans = 0
for i in range(n):
	ans += prf[i] * a[i]
print(ans)


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


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def msi():
	return map(str, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(100000000)
	threading.stack_size(40960000)
	thread = threading.Thread(target=main)
	thread.start()
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[1]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def main():
	(n, q) = mi()
	a = li()
	pre = [0] * (n + 5)
	a.sort(reverse=True)
	for i in range(q):
		(x, y) = mi()
		pre[x] += 1
		pre[y + 1] -= 1
	for i in range(1, n + 2):
		pre[i] += pre[i - 1]
	l = []
	for i in range(1, n + 1):
		l.append([pre[i], i])
	l.sort(reverse=True)
	new = [0] * (n + 5)
	ans = 0
	for i in range(n):
		new[l[i][1]] = a[i]
		ans += l[i][0] * a[i]
	print(ans)
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):
	(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()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys

def main():
	(n, q) = map(int, input().strip().split())
	A = list(map(int, input().strip().split()))
	A.sort()
	M = [0] * n
	XX = sys.stdin.read().strip().split()
	for i in range(0, len(XX), 2):
		(l, r) = (int(XX[i]), int(XX[i + 1]))
		l = l - 1
		M[l] = M[l] + 1
		if r < n:
			M[r] = M[r] - 1
	for i in range(1, n):
		M[i] = M[i - 1] + M[i]
	M.sort()
	s = 0
	for i in range(n):
		s += M[i] * A[i]
	print(s)
main()


intin = lambda : map(int, input().split())
Ain = lambda : list(map(int, input().split()))
(n, q) = intin()
a = Ain()
p = [0] * n
for i in range(q):
	(x, y) = intin()
	if y - 1 >= 0:
		p[y - 1] += 1
	if x - 2 >= 0:
		p[x - 2] -= 1
i = n - 2
while i >= 0:
	p[i] += p[i + 1]
	i -= 1
p.sort()
a.sort()
ans = 0
i = 0
while i < n:
	ans += a[i] * p[i]
	i += 1
print(ans)


from sys import stdin, stdout
(n, q) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
f = [0] * (n + 1)
for _ in range(q):
	(l, r) = map(int, stdin.readline().split())
	f[l - 1] += 1
	f[r] -= 1
for i in range(1, n + 1):
	f[i] += f[i - 1]
f.pop()
a.sort()
f.sort()
ans = 0
for i in range(n):
	ans += a[i] * f[i]
stdout.write(str(ans))


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)
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)


def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return [str(x) for x in stdin.readline().split()]
from sys import stdin
from collections import *
(n, q) = arr_inp(1)
(a, cum) = (sorted(arr_inp(1), reverse=True), defaultdict(int))
for i in range(q):
	(x, y) = arr_inp(1)
	cum[x] += 1
	cum[y + 1] -= 1
for i in range(2, n + 1):
	cum[i] += cum[i - 1]
(all, ans) = (sorted(cum.values(), reverse=True), 0)
for i in range(n):
	ans += all[i] * a[i]
print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def main():
	(n, q) = LI()
	a = sorted(LI())
	aa = [LI_() for _ in range(q)]
	r = [0] * (n + 1)
	for (b, c) in aa:
		r[b] += 1
		r[c + 1] -= 1
	for i in range(1, n):
		r[i] += r[i - 1]
	d = sorted(r[:-1])
	k = 0
	for i in range(n):
		k += d[i] * a[i]
	return k
print(main())


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
val = [0 for _ in range(n + 1)]
b = [0 for i in range(n)]
v = 0
for i in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	val[x] += 1
	val[y] -= 1
for i in range(n):
	v += val[i]
	b[i] = v
b.sort(reverse=True)
msum = 0
for j in range(n):
	msum += a[j] * b[j]
print(msum)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, q) = I()
l = I()
ar = [0] * (n + 1)
for i in range(q):
	(x, y) = I()
	x -= 1
	y -= 1
	ar[x] += 1
	ar[y + 1] -= 1
for i in range(1, len(ar)):
	ar[i] += ar[i - 1]
ar.sort(reverse=True)
l.sort(reverse=True)
ans = 0
for i in range(n):
	ans += l[i] * ar[i]
print(ans)


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = sorted(arr)
freq = [0] * (n + 1)
sum1 = 0
for i in range(q):
	(l, r) = arr = map(int, input().split())
	freq[l - 1] += 1
	freq[r] -= 1
for i in range(1, len(freq)):
	freq[i] = freq[i] + freq[i - 1]
freq = sorted(freq[:n])
for i in range(len(arr1)):
	sum1 = sum1 + freq[i] * arr1[i]
print(sum1)


from sys import *
arr = [int(x) for x in stdin.readline().split()]
(n, q) = (arr[0], arr[1])
a = [int(x) for x in stdin.readline().split()]
b = [0] * (n + 2)
for i in range(q):
	arr = [int(x) for x in stdin.readline().split()]
	(l, r) = (arr[0], arr[1])
	b[l] += 1
	b[r + 1] -= 1
sn = 0
for i in range(1, n + 1):
	sn += b[i]
	b[i] = sn
a.sort(reverse=True)
b.sort(reverse=True)
sn = 0
for i in range(n):
	sn += a[i] * b[i]
print(sn)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
arr = [int(i) for i in input().split()]
arr.sort()
maxfreq = [0] * n
minfreq = [0] * n
for i in range(q):
	(l, r) = map(int, input().split())
	maxfreq[l - 1] += 1
	minfreq[r - 1] += 1
freq = [0] * n
val = 0
for i in range(n):
	val += maxfreq[i]
	freq[i] += val
	val -= minfreq[i]
freq.sort()
sum_ = 0
for i in range(n):
	sum_ += freq[i] * arr[i]
print(sum_)