CodeEff/ECCO huggingface dataset:
# Original solution
import bisect

N, M = list(map(int,input().split()))

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

BC = []

for i in range(M):
    BC.append(list(map(int,input().split())))

BC = sorted(BC, key=lambda x: x[1])

BC.reverse()

for i in range(M):
    B, C = BC[i]
    in_idx = bisect.bisect_right(A,C)

    if B >= in_idx:
        A = [C]*in_idx + A[in_idx:]
        break
    else:
        A = A[B:in_idx] + [C]*B + A[in_idx:]

print((sum(A)))

# Optimized solution
N, M = list(map(int,input().split()))

A = [-1]
A += list(map(int,input().split()))
A.sort()

BC = [[1,-1]]

for i in range(M):
    BC.append(list(map(int,input().split())))

BC = sorted(BC, key=lambda x: x[1])


x = 0

for i in range(N):
    if A[-1] > BC[-1][1]:
        x += A.pop()
        
    else:
        x += BC[-1][1]
        BC[-1][0] -= 1
        if BC[-1][0] == 0:
            BC.pop()

print(x)
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
l = []
all_set = a
for _ in range(m):
#    l.append(list(map(int, input().split())))
    bi, ci = list(map(int, input().split()))
    for _ in range(bi):
        all_set.append(ci)
    
print((sum(sorted(all_set, reverse=True)[:n])))

# Optimized solution
# coding: utf-8
# Your code here!

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

l = []
for _ in range(m):
    l.append(list(map(int, input().split())))
    
l = sorted(l, key=lambda x:x[1], reverse=True)

top_n = []
flag = False
for bi, ci in l:
    for _ in range(bi):
        if len(top_n) < n:
            top_n.append(ci)
        else:
            flag = True
    if flag:
        break
a.extend(top_n)

print((sum(sorted(a, reverse=True)[:n])))
# Original solution
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
bc = []
for i in range(M):
    bc.append(list(map(int,input().split())))

A = sorted(A,reverse=True)
bc = sorted(bc,key=lambda x : x[1],reverse=True)

AA = []
for i in range(M):
    l = [bc[i][1]]*bc[i][0]
    AA += l

AA = sorted(AA)
AAA = []
for i in range(1,min(len(A),len(AA))+1):
    if A[-i] < AA[-i]:
        AAA.append(AA[-i])
    else:
        AAA.append(A[-i])
if len(A) >= len(AA):
    AAA += A[:N-len(AAA)]
print((sum(AAA)))


# Optimized solution
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = sorted(A)
bc = []
for i in range(M):
    bc.append(list(map(int,input().split())))

bc = sorted(bc,key=lambda x : -x[1])
i = 0
for b,c in bc:
    for j in range(i,min(N,i+b)):
        if A[j] < c:
            A[j] = c
    i += b
print((sum(A)))
# Original solution
N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
B = sorted([list(map(int,input().split())) for _ in range(M)],key=lambda x:x[1],reverse=True)
cur = 0
cnt = 0
for i in range(N):
    if A[i]<B[cur][1] and cnt<B[cur][0]:
        A[i]=B[cur][1]
        cnt += 1
    elif A[i]>=B[cur][1]:break
    elif cnt>=B[cur][0]:
        cur += 1
        cnt = 0
        if cur>=M:break
        if A[i]<B[cur][1]:
            A[i] = B[cur][1]
            cnt += 1
print((sum(A)))

# Optimized solution
N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
B = sorted([list(map(int,input().split())) for _ in range(M)],key=lambda x:x[1],reverse=True)
cur = 0
cnt = B[0][0]
for i in range(N):
    a = A[i]
    if cur<M and B[cur][1]>a:
        if cnt>0:
            A[i] = B[cur][1]
            cnt -= 1
        else:
            cur += 1
            if cur<M:
                cnt = B[cur][0]
                if B[cur][1]>a:
                    A[i] = B[cur][1]
                    cnt -= 1
print((sum(A)))
# Original solution
"""
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for _ in range(m)]
b.sort(key = lambda x : x[1], reverse = True)
a.sort()
i = 0
j = 0
c = 1
ans = sum(a)
while True:
    if i >= m:
        break
    for _ in range(b[i][0]):
        if j >= n:
            c = 0
            break
        if a[j] < b[i][1]:
            ans += b[i][1] - a[j]
            j += 1
        else:
            c = 0
            break
    i += 1
    if c == 0:
        break
print(ans)
"""
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for _ in range(m)]
b.sort(key = lambda x : x[1], reverse = True)
c = n
for i in range(m):
    if c - b[i][0] >= 0:
        a = a + ([b[i][1]] * b[i][0])
        c -= b[i][0]
    else:
        a = a + ([b[i][1]] * c)
        break
a.sort(reverse = True)
print((sum(a[0 : n])))

# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = []
for _ in range(m):
    b, c = list(map(int, input().split()))
    bc.append([c, b])
a.sort()
bc.sort(reverse = True)
x = [0] * n
i, j = 0, 0
while i < n:
    for _ in range(bc[j][1]):
        x[i] = bc[j][0]
        i += 1
        if i == n:
            break
    j += 1
    if j == m:
        break
ans = 0
for i in range(n):
    ans += max(a[i], x[i])
print(ans)
# Original solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = inpl()
a.sort()
bc = [inpl() for _ in range(m)]
bc.sort(key = lambda x:x[1], reverse = True)
lm = sum(x[1] for x in bc)
now = 0
alt = 0
while now < n and alt < m:
    c,b = bc[alt]
    if a[now] > b:
        break
    else:
        a[now] = b
    bc[alt][0] -= 1
    if bc[alt][0] == 0:
        alt += 1
    now += 1
print((sum(a)))


# Optimized solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = inpl()
a.sort()
bc = [inpl() for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse = True)
ind = -1
now = -1
cnt = 0
for i in range(n):
    if cnt == 0:
        ind += 1
        if ind >= m: break
        cnt, now = bc[ind]
    if a[i] >= now:
        break
    a[i] = now
    cnt -= 1
print((sum(a)))
# Original solution
n, m = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))

d = []
for i in range(m):
    b, c = list(map(int, input().split()))
    d.extend([c]*b)

d.sort(reverse=True)

for i in range(min(n, len(d))):
    if a[i] >= d[i]:
        break
    a[i] = d[i]

print((sum(a)))

# Optimized solution
n, m = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))

op = []
for i in range(m):
    b, c = list(map(int, input().split()))
    op.append((c, b))

op.sort(reverse=True)

j = 0
k = 0

for i in range(n):
    if a[i] >= op[j][0]:
        break

    a[i] = op[j][0]
    k += 1

    if k >= op[j][1]:
        j += 1
        k = 0

    if j >= m:
        break

print((sum(a)))
# Original solution
import heapq
def solve():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    BC = [list(map(int, input().split())) for i in range(M)]

    A.sort()
    BC.sort(key=lambda x: x[1], reverse=True)
    BC2 = []

    for bc in BC:
        for i in range(bc[0]):
            BC2.append(bc[1])
    
    BC_idx = 0
    for i in range(N):
        if BC_idx >= len(BC2):
            break
        if A[i] < BC2[BC_idx]:
            A[i] = BC2[BC_idx]
            BC_idx += 1

    print((sum(A)))

if __name__ == '__main__':
    solve()

# Optimized solution
def solve():
    N, M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    A.sort()
    operate = []
    for _ in range(M):
        b, c = list(map(int,input().split()))
        operate.append([b,c])
    operate.sort(reverse=True, key=lambda x:x[1])    

    rewrite = [0] * N
    idx = 0
    for b,c in operate:
        for i in range(b):
            rewrite[idx] = c
            idx += 1
            if idx == N:
                break
        if idx == N:
            break
    
    ans = 0
    for i in range(N):
        ans += max(A[i],rewrite[i])
    
    print(ans)

if __name__ == '__main__':
    solve()
# Original solution
def main():
  from bisect import bisect_left
  n,m=list(map(int,input().split()))
  a=sorted(list(map(int,input().split())))
  for _ in range(m):
    b,c=list(map(int,input().split()))
    index = bisect_left(a,c)
    b=index if b>=index else b
    a=[c]*b+a[b:]
    a.sort()
  print((sum(a)))
if __name__=='__main__':
  main()

# Optimized solution
def main():
  n,m=list(map(int,input().split()))
  a=sorted(list(map(int,input().split())))
  bc=[list(map(int,input().split())) for _ in range(m)]
  for i in range(n):
    bc.append([1,a[i]])
  bc.sort(key=lambda x:x[1],reverse=True)
  ans,cnt=0,0
  for i in range(n):
    ans+=bc[i][0]*bc[i][1]
    cnt+=bc[i][0]
    if cnt>=n:
      ans-=(cnt-n)*bc[i][1]
      break
  print(ans)
if __name__=='__main__':
  main()
# Original solution
import heapq

N, M = list(map(int, input().split()))
A = [int(i) for i in input().split()]
A.sort()
A.append(0)
S = []
heapq.heapify(S)
c = A[0]
cnt = 1
for i in range(1, N + 1):
    if A[i] == c:
       cnt += 1
    else:
        heapq.heappush(S, (A[i - 1], cnt))
        cnt = 1
        c = A[i]


for i in range(M):
    B, v = list(map(int, input().split()))
    while len(S) > 0 and S[0][0] < v:
        x = heapq.heappop(S)
        if B <= x[1]:
            heapq.heappush(S, (v, B))
            if not B == x[1] : heapq.heappush(S, (x[0], x[1] - B))
            break
        else:
            B -= x[1]
            heapq.heappush(S, (v, x[1]))
sumS = 0
while len(S) > 0:
    x = heapq.heappop(S)
    sumS += x[0] * x[1]
print(sumS)

# Optimized solution
import heapq

N, M = list(map(int, input().split()))
A = [int(i) for i in input().split()]
A.sort()
A.append(0)
S = []
heapq.heapify(S)
c = A[0]
cnt = 1
for i in range(1, N + 1):
    if A[i] == c:
       cnt += 1
    else:
        heapq.heappush(S, (A[i - 1], cnt))
        cnt = 1
        c = A[i]


for i in range(M):
    B, v = list(map(int, input().split()))
    flag = False #Sからの取り出し比較を1度以上終えているか
    b = B # 残りカード
    while len(S) > 0 and S[0][0] < v:
        x = heapq.heappop(S)
        if b <= x[1]:
            heapq.heappush(S, (v, B))
            if not b == x[1] : heapq.heappush(S, (x[0], x[1] - b))
            flag = False
            break
        else:
            flag = True
            b -= x[1]

    if flag: #交換しきらないで、途中で終わっているのでこの分は挿入する
        heapq.heappush(S, (v, B - b))

sumS = 0
while len(S) > 0:
    x = heapq.heappop(S)
    sumS += x[0] * x[1]
print(sumS)
# Original solution
import heapq

N, M = list(map(int, input().split()))
A = [int(i) for i in input().split()]
A.sort()
A.append(0)
S = []
heapq.heapify(S)
c = A[0]
cnt = 1
for i in range(1, N + 1):
    if A[i] == c:
       cnt += 1
    else:
        heapq.heappush(S, (A[i - 1], cnt))
        cnt = 1
        c = A[i]


for i in range(M):
    B, v = list(map(int, input().split()))
    flag = False #Sからの取り出し比較を1度以上終えているか
    b = B # 残りカード
    while len(S) > 0 and S[0][0] < v:
        x = heapq.heappop(S)
        if b <= x[1]:
            heapq.heappush(S, (v, B))
            if not b == x[1] : heapq.heappush(S, (x[0], x[1] - b))
            flag = False
            break
        else:
            flag = True
            b -= x[1]

    if flag: #交換しきらないで、途中で終わっているのでこの分は挿入する
        heapq.heappush(S, (v, B - b))

sumS = 0
while len(S) > 0:
    x = heapq.heappop(S)
    sumS += x[0] * x[1]
print(sumS)









# Optimized solution
N, M = list(map(int, input().split()))
A = [int(i) for i in input().split()]
D = []

for i in range(M):
    b, c = list(map(int, input().split()))
    D.append((c, b))
A.sort()
D.sort(reverse=True)
i = 0
for c, b in D:
    for j in range(i, min(i + b, N)):
        A[j] = max(c, A[j])
    i += b

print((sum(A)))
# Original solution


def read_input():
    n, m = list(map(int, input().split()))
    alist = list(map(int, input().split()))

    clist = []
    for i in range(m):
        b, c = list(map(int, input().split()))

        clist.extend([c]*b)

    return alist, clist

def submit():
    alist, clist = read_input()

    alist.sort(reverse=False)
    clist.sort(reverse=True)

    j = 0
    result = 0
    for a in alist:
        if j >= len(clist):
            result += a
        elif a >= clist[j]:
            result += a
        else:
            result += clist[j]
            j += 1

    print(result)



if __name__ == '__main__':
    submit()


# Optimized solution


def read_input():
    n, m = list(map(int, input().split()))
    alist = list(map(int, input().split()))

    clist = []
    for i in range(m):
        b, c = list(map(int, input().split()))
        clist.append([c, b])

    return alist, clist

def submit():
    alist, clist = read_input()

    alist.sort(reverse=False)
    clist.sort(key=lambda x: x[0], reverse=True)

    j = 0
    result = 0
    for a in alist:
        if j >= len(clist):
            result += a
        elif a >= clist[j][0]:
            result += a
        else:
            if clist[j][1] > 0:
                result += clist[j][0]
                clist[j][1] -= 1
                if clist[j][1] == 0:
                    j += 1

    print(result)



if __name__ == '__main__':
    submit()
# Original solution
#!/usr/bin/env python3.4

# abc127_d

import collections
import itertools
import functools

def find_index(iterable, func, from_i):
    i = from_i
    l = len(iterable)
    while i<l and not func(iterable[i]):
        i += 1
    return i

def insert(deq, i, x):
    l = len(deq)
    if i < l/2:
        deq.rotate(-i)
        deq.appendleft(x)
        deq.rotate(i)
    else:
        k = l-i
        deq.rotate(k)
        deq.append(x)
        deq.rotate(-k)

def main():
    # Input
    _, m = [int(s) for s in input().split()]
    cards = [int(s) for s in input().split()]
    acts = [[int(s) for s in input().split()] for _ in range(m)]
    # Get ans
    cards = collections.deque(sorted(cards))
    acts.sort(key=lambda a: a[1])
    i = 0
    for b, c in acts:
        i = find_index(cards, lambda card: card>=c, i)
        #print(i, cards[:i], cards[i:])
        change_num = min(b, i)
        #cards = cards[:i][change_num:] + [c]*change_num + cards[i:]
        for _ in range(change_num):
            insert(cards, i, c)
            cards.popleft()
        #print(cards)
    ans = sum(cards)
    # Output
    print(ans)

if __name__ == '__main__':
    main()



# Optimized solution
#!/usr/bin/env python3.4

# abc127_d

import collections
import itertools
import functools

def main():
    # Input
    _, m = [int(s) for s in input().split()]
    cards = [int(s) for s in input().split()]
    acts = [[int(s) for s in input().split()] for _ in range(m)]
    # Get ans
    cards = collections.deque(sorted(cards))
    acts.sort(key=lambda a: a[1], reverse=True)
    for b, c in acts:
        for _ in range(b):
            if cards[0] >= c:
                break
            cards.popleft()
            cards.append(c)
    ans = sum(cards)
    # Output
    print(ans)

if __name__ == '__main__':
    main()
# Original solution
#!/usr/bin/env python3.4

# abc127_d

import collections
import itertools
import functools

def main():
    # Input
    _, m = [int(s) for s in input().split()]
    cards = [int(s) for s in input().split()]
    acts = [[int(s) for s in input().split()] for _ in range(m)]
    # Get ans
    cards = collections.deque(sorted(cards))
    acts.sort(key=lambda a: a[1], reverse=True)
    for b, c in acts:
        for _ in range(b):
            if cards[0] >= c:
                break
            cards.popleft()
            cards.append(c)
    ans = sum(cards)
    # Output
    print(ans)

if __name__ == '__main__':
    main()



# Optimized solution
#!/usr/bin/env python3.4

# abc127_d

import collections

def main():
    # Input
    n, m = [int(s) for s in input().split()]
    cards = [int(s) for s in input().split()]
    acts = [[int(s) for s in input().split()] for _ in range(m)]
    # Get ans
    cards = collections.deque(sorted(cards), n)
    acts.sort(key=lambda a: a[1], reverse=True)
    for b, c in acts:
        for _ in range(b):
            if cards[0] >= c:
                break
            cards.append(c)
    ans = sum(cards)
    # Output
    print(ans)

if __name__ == '__main__':
    main()
# Original solution
import heapq
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
heapq.heapify(A)
for i in range(M):
  b, c = list(map(int, input().split()))
  for j in range(b):
    a = heapq.heappop(A)
    if a < c:
      heapq.heappush(A, c)
    else:
      heapq.heappush(A, a)
      break
print((sum(A)))

# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
B = []
for i in range(M):
  b, c = list(map(int, input().split()))
  B.append([c, b])
B.sort(reverse=True)
i = 0
f = 0
for j in range(M):
  while B[j][1]:
    if A[i] < B[j][0]:
      A[i] = B[j][0]
      B[j][1] -= 1
      i += 1
      if i >= N:
        f = 1
        break
    else:
      f = 1
      break
  if f == 1:
    break
print((sum(A)))
# Original solution
import heapq
N, M = list(map(int, input().split()))
nums = list(map(int, input().split()))
n = len(nums)
heap = []
for i in range(M):
    B, C = list(map(int, input().split()))
    heap.append([-C, B])
for num in nums:
    heap.append([-num, 1])
s = 0
heapq.heapify(heap)
while n > 0:
    num, cnt = heapq.heappop(heap)
    num = num * -1
    s += num * min(cnt, n)
    n -= min(cnt, n)
print(s)

# Optimized solution
def getInput():
    return [int(x) for x in input().split()]

N, M = getInput()
nums = getInput()
nums = sorted(nums)
rep = []
for i in range(M):
    b, c = getInput()
    rep.append((b, c))
rep = sorted(rep, key=lambda x: x[1], reverse=True)
ans = 0
minIndex = 0
isFinished = False
for b, c in rep:
    for _ in range(b):
        if minIndex < len(nums) and nums[minIndex] < c:
            ans += c
            minIndex += 1
        else:
            isFinished = True
            break
    
    if isFinished:
        break
if minIndex < len(nums):
    ans += sum(nums[minIndex:])
print(ans)
# Original solution
import bisect

n,m = list(map(int,input().split()))
lst = list(map(int,input().split()))
lst.sort()

for i in range(m):
    b,c = list(map(int,input().split()))
    pos = bisect.bisect_left(lst,c)
    for j in range(min(b,pos)):
        lst[j] = c
    lst.sort()
print((sum(lst)))

# Optimized solution
n,m = list(map(int,input().split()))
l_a = sorted(list(map(int,input().split())))
l_bc = [list(map(int,input().split())) for _ in range(m)]
l_bc.sort(key = lambda x:x[1],reverse = True)
for b,c in l_bc:
    l_a.extend([c]*b)
    if len(l_a) > 2*n:
        break

l_a.sort(reverse = True)
print((sum(l_a[:n])))
# Original solution
n,m = list(map(int,input().split()))
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]
ans = 0
cnt = 0
d = {}

for i in range(n): 
    d[a[i]] = d.get(a[i],0)+1
for k in d: 
    bc.append([d[k],k])
bc.sort(key= lambda x:x[1],reverse=True)

for i in range(len(bc)):
    if cnt < n:
        ans += bc[i][1]*bc[i][0]
        cnt += bc[i][0]
    else:
        ans -= (cnt-n)*bc[i-1][1]
        break
else:
    ans -= (cnt-n)*bc[i][1]

print(ans)


# Optimized solution
n,m = list(map(int,input().split()))
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
d = []
cnt1 = 0
cnt2 = 0
x = 0

for lst in bc:
    cnt2 = 0
    while cnt1 < n and cnt2 < lst[0]:
        d.append(lst[1])
        cnt1 += 1
        cnt2 += 1

for i in range(len(d)):
    if d[i] - a[i] < 0:
        x = i
        break
else:
    x += i+1

print((sum(d[:x]+a[x:])))
# Original solution
n,m = list(map(int,input().split()))
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
d = []
cnt1 = 0
cnt2 = 0
x = 0

for lst in bc:
    cnt2 = 0
    while cnt1 < n and cnt2 < lst[0]:
        d.append(lst[1])
        cnt1 += 1
        cnt2 += 1

for i in range(len(d)):
    if d[i] - a[i] < 0:
        x = i
        break
else:
    x += i+1

print((sum(d[:x]+a[x:])))

# Optimized solution
n,m = list(map(int,input().split()))
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
d = []
cnt1 = 0
cnt2 = 0
x = 0

for lst in bc:
    cnt2 = 0
    while cnt1 < n and cnt2 < lst[0]:
        d.append(lst[1])
        cnt1 += 1
        cnt2 += 1
    if cnt1 == n:
        break

for i in range(len(d)):
    if d[i] - a[i] < 0:
        x = i
        break
else:
    x += i+1

print((sum(d[:x]+a[x:])))
# Original solution
from operator import itemgetter

n, m = [int(i) for i in input().split()]
a = sorted([int(i) for i in input().split()])
#print(a)

bc = []
for _ in range(m):
  bc.append([int(i) for i in input().split()])
bc = sorted(bc, key=itemgetter(1), reverse=True)
#print(bc)

ans = 0
for b,c in bc:
  #print(a,b,c)
  lower_c_num = 0
  for a_i in a:
    if a_i < c:
      lower_c_num += 1
      if lower_c_num > b:
        lower_c_num = b
        break
    else:
      break
    
  change = min(b, lower_c_num)
  a = a[change:]
  ans += c * change
  if len(a) == 0:
    break
  if change != b:
    break
    
ans += sum(a)

print(ans)
    

# Optimized solution
from operator import itemgetter

n, m = [int(i) for i in input().split()]
a = sorted([int(i) for i in input().split()])
#print(a)

bc = []
for _ in range(m):
  bc.append([int(i) for i in input().split()])
bc = sorted(bc, key=itemgetter(1), reverse=True)
#print(bc)

change = []
for b,c in bc:
  len_change = len(change)
  b_up = b
  if n - len_change < b:
    b_up = n - len_change
  #print(b_up)
  change += [c]*b_up
  if b_up != b:
    break
change += [0]*(n-len(change))

ans = 0
for i in range(n):
  #print(ans)
  #print(i)
  if a[i] < change[i]:
    ans += change[i]
  else:
    ans += sum(a[i:])
    break
    
print(ans)
# Original solution
import heapq

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

if N == 1:
    print((max(A[0], BC[0][1])))
    quit()

heapq.heapify(A)
for b, c in BC:
    a = A[0]
    if a >= c:
        continue
    else:
        curPopped = 0
        while curPopped < b:
            a = heapq.heappop(A)
            if a >= c:
                heapq.heappush(A, a)
                break
            curPopped += 1
        for i in range(curPopped):
            heapq.heappush(A, c)

print((sum(A)))

# Optimized solution

import heapq

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: x[1], reverse=True)

if N == 1:
    print((max(A[0], BC[0][1])))
    quit()

heapq.heapify(A)
for b, c in BC:
    a = A[0]
    if a >= c:
        continue
    else:
        curPopped = 0
        while curPopped < b:
            a = heapq.heappop(A)
            if a >= c:
                heapq.heappush(A, a)
                break
            curPopped += 1
        for i in range(curPopped):
            heapq.heappush(A, c)

print((sum(A)))
"""
import bisect
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = [list(map(int, input().split())) for i in range(M)]

if N == 1:
    print(max(A[0], BC[0][1]))
    quit()

for b, c in BC:
    a = A[0]
    if a >= c:
        continue
    else:
        l = bisect.bisect_left(A, c)
        print(l)
        l = min(b, l)
        A = A[l:] + [c] * l
        print(l, A)

print(sum(A))
"""