CodeEff/ECCO huggingface dataset:
# Original solution
from collections import deque
N, M = list(map(int, input().split()))

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

for i in range(M):
    B, C = list(map(int, input().split()))
    A.extend([C]*B)

E = list(A)
E.sort(reverse = True)

print((sum(E[:N]))) 

# Optimized solution
from collections import deque
N, M = list(map(int, input().split()))

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

for i in range(M):
    B, C = list(map(int, input().split()))
    if C >= min(A):
        A.extend([C]*B)

E = list(A)
E.sort(reverse = True)

print((sum(E[:N])))
# Original solution
import heapq

n, m = list(map(int, input().split()))
queue = []
for a in map(int, input().split()):
  heapq.heappush(queue, a)
for _ in range(m):
  b, c = list(map(int, input().split()))
  for _ in range(b):
    if queue[0] < c:
      heapq.heapreplace(queue, c)
    else:
      break
print((sum(queue)))

# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
cb = [list(map(int, input().split()[::-1])) for _ in range(m)]
a.sort()
cb.sort()
summation = 0
a_tmp = a.pop()
cb_tmp = cb.pop()
for i in range(n):
  if a_tmp >= cb_tmp[0]:
    summation += a_tmp
    if a:
      a_tmp = a.pop()
  else:
    summation += cb_tmp[0]
    cb_tmp[1] -= 1
    if cb_tmp[1] == 0:
      if cb:
        cb_tmp = cb.pop()
      else:
        cb_tmp = [0, n]
print(summation)
# Original solution
from bisect import bisect_left
from heapq import heappop, heappush

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

BC = []

for i in range(M):
  b, c = list(map(int, input().split()))
  heappush(BC, (-c, b))

for i in range(M):
  mc, b = heappop(BC)
  c = -mc
  index = bisect_left(A, c)

  if index == 0:
    continue
  
  if index <= b:
    A = [c for _ in range(index) ] + A[index:]
  else:
    A = [c for _ in range(b)] + A[b:]
  
  A.sort()

print((sum(A)))

# Optimized solution
from heapq import heappop, heappush, heapify

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
heapify(A)
BC = []

for i in range(M):
  b, c = list(map(int, input().split()))
  heappush(BC, (-c, b))

for i in range(M):
  mc, b = heappop(BC)
  c = -mc
  end = False

  for j in range(b):
    min = heappop(A)
    if c <= min:
      heappush(A, min)
      end = True
      break
    else:
      heappush(A, c)

  if end:
    break

print((sum(A)))
# Original solution
import heapq
push, pop = heapq.heappush, heapq.heappop

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

heapq.heapify(a)
for _ in range(m):
    b,c = list(map(int, input().split()))
    for _ in range(b):
        p = pop(a)
        if p < c:
            push(a, c)
        else:
            # キューに戻す
            push(a, p)
            break
print((sum(a)))

# Optimized solution
import heapq
push, pop = heapq.heappush, heapq.heappop

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

def modify():
    heapq.heapify(a)
    
    bc = [list(map(int, input().split())) for _ in range(m)]
    bc.sort(key=lambda x:x[1], reverse=True)
    
    for b,c in bc:
        for _ in range(b):
            p = pop(a)
            if p < c:
                push(a, c)
            else:
                # キューに戻す
                push(a, p)
                return

modify()            
print((sum(a)))
# Original solution
n, m = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
mat = []
for _ in range(m):
    b, c = list(map(int, input().split()))
    mat.extend([c] * b)
mat = sorted(mat, reverse=True)[:n]
for i, t in enumerate(a):
    if i == len(mat):
        break
    if t < mat[i]:
        a[i] = mat[i]
    else:
        break

print((sum(a)))


# Optimized solution
n, m = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
bc = [[0] * 2 for _ in range(m)]
for i in range(m):
    bc[i] = list(map(int, input().split()))
bc = sorted(bc, key=lambda x: x[1], reverse=True)
mat = []
for b, c in bc:
    if len(mat) + b > n:
        mat.extend([c] * (n - len(mat)))
        break
    else:
        mat.extend([c]*b)

for i, t in enumerate(a):
    if i == len(mat):
        break
    if t < mat[i]:
        a[i] = mat[i]
    else:
        break

print((sum(a)))
# Original solution

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


for i in range(M):
    B,C = list(map(int,input().split()))
    
    A.extend([C]*B)
b=sorted(A)
print((sum(b[-N:])))

# Optimized solution
import sys
input = sys.stdin.readline


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


for i in range(M):
    B,C = list(map(int,input().split()))
    
    A.extend([C]*B)
b=sorted(A)
print((sum(b[-N:])))
# Original solution
import bisect
import sys
input = sys.stdin.readline
def main():
    N,M = list(map(int,input().split()))
    A= list(map(int,input().split()))
    A = sorted(A)

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

    for B,C in BC:
        index = bisect.bisect_right(A,C)
        if index==0:
            break
        if index > B:
            A = A[B:index] + [C] *B + A[index:]
        else:
            A = [C]*index + A[index:]

    print((sum(A)))
    
if __name__ == '__main__':
    main()

# Optimized solution
import sys
input = sys.stdin.readline
def main():
    N,M = list(map(int,input().split()))
    A= list(map(int,input().split()))
    A = sorted(A)

    BC=[list(map(int,input().split())) for i in range(M)]
    BC = sorted(BC, key=lambda x: x[1],reverse=True)
    index=0
    max_index=len(A)
    
    for B,C in BC:
        temp = [C]*B
        for t in temp:
            if max_index>index and  t>A[index]:
                A[index] = t
            else:
                return A
            index+=1
    return A
    
if __name__ == '__main__':
    A=main()
    print((sum(A)))
# Original solution
import heapq


n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
h = []
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1
    

for i in range(m):
    b, c = list(map(int, input().split()))
    
    if c not in ad:
        ad[c] = b
    else:
        ad[c] += b


keys = list( ad.keys() )
keys.sort(reverse=True)



for k in keys:
    for i in range(ad[k]):
        heapq.heappush(h, k)

    if len(h) >= n:
        break


ans = sum( heapq.nlargest(n, h) )
print(ans)

# Optimized solution
import heapq


n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
h = []
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1
    

for i in range(m):
    b, c = list(map(int, input().split()))
    
    if c not in ad:
        ad[c] = b
    else:
        ad[c] += b


keys = list( ad.keys() )
keys.sort(reverse=True)



for k in keys:
    for i in range(ad[k]):
        heapq.heappush(h, k)

        if len(h) >= n:
            break


ans = sum( heapq.nlargest(n, h) )
print(ans)
# Original solution
import heapq

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
origin = sum(A)
heapq.heapify(A)

for _ in range(M):
    b, c = list(map(int, input().split()))
    for _ in range(b):
        smallest = heapq.heappop(A)
        tmp = c - smallest
        if tmp <= 0:
            heapq.heappush(A, smallest)
            break
        else:
            heapq.heappush(A, c)
            origin += tmp

print(origin)


# Optimized solution
import sys
import heapq

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
origin = sum(A)
heapq.heapify(A)

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

count = 0

for i in range(M):
    b = BC[i][0]
    c = BC[i][1]
    for _ in range(b):
        smallest = heapq.heappop(A)
        tmp = c - smallest
        if tmp <= 0:
            heapq.heappush(A, smallest)
            break
        else:
            heapq.heappush(A, c)
            origin += tmp
            count += 1
            if count >= N:
                print(origin)
                sys.exit()

print(origin)
# Original solution
import heapq

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
print((sum(a)))


# Optimized solution
import heapq

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x: -x[1])
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
            break
print((sum(a)))
# Original solution
# sys.stdin.readline()
import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)
for _ in range(m):
    b, c= list(map(int, input().split()))
    if a[n-1] < c:
        for i in range(min(b,n)):
            a.append(c)
        a.sort(reverse=True)
print((sum(a[:n])))

# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

for i in range(m):
 a.sort()
 b,c=list(map(int, input().split()))
 for i in range(b):
  if a[i] < c:
   a[i] = c
  else:
   break
print((sum(a)))

# Optimized solution
n,m=list(map(int,input().split()))
l=[[int(x),1] for x in input().split()]
for i in range(m):
  b,c=list(map(int,input().split()))
  l.append([c,b])

s = sorted(l, key=lambda x:x[0], reverse=True)

c=n
t=0
i=0
while c>0:
  n = s[i][1] if c>=s[i][1] else c
  t += s[i][0] * n
  c -= n
  i += 1

print(t)
# Original solution
from collections import defaultdict
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
d=defaultdict(int)
a.sort()

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

d_sorted=sorted(list(d.items()),reverse=True, key=lambda x:x[0])
l=[]

for i,j in d_sorted:
    for k in range(j):
        l.append(i)
    if len(l)>=n:
        break

for i in range(min(n, len(l))):
    a[i]=max(a[i],l[i])

print((sum(a)))

# Optimized solution
from collections import defaultdict
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
d=defaultdict(int)
a.sort()

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

d_sorted=sorted(list(d.items()),reverse=True, key=lambda x:x[0])
l=[]

for i,j in d_sorted:
    for k in range(j):
        l.append(i)
        if len(l)>n:
            break
    else:
        continue
    break
for i in range(min(n, len(l))):
    a[i]=max(a[i],l[i])

print((sum(a)))
# Original solution
import heapq

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

B = []
C = []
BC = []

A.sort()

for i in range(M):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)
    BC.append([b, c])


sorted(BC, key=lambda x: x[1])
BC = BC[::-1]
C = C.sort()

heapq.heapify(A)

# print(A)
# print(BC)

buff = []
counter = 0
for i in range(M):
    # if counter > N*2:
    #     break
    for j in range(BC[i][0]):
        # buff.append(BC[i][1])
        # counter += 1
        heapq.heappush(A, BC[i][1])
        heapq.heappop(A)
        if counter > N*2:
            break

# A = A + buff
# A.sort()
# A = A[::-1]
# print(A)
print((sum(A)))

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

B = []
C = []
BC = []

A.sort()

for i in range(M):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)
    BC.append([b, c])


BC = sorted(BC, key=lambda x: x[1])
BC = BC[::-1]
C = C.sort()

# print(A)
# print(BC)

buff = []
counter = 0
for i in range(M):
    if counter > N*2:
        break
    for j in range(BC[i][0]):
        buff.append(BC[i][1])
        counter += 1
        if counter > N*2:
            break

A = A + buff
A.sort()
A = A[::-1]
print((sum(A[:N])))
# 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):
        if c > a[0]:
            heapq.heapreplace(a, c)
        else:
            break

print((sum(a)))

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

cnt = {}

for i in range(n):
    if a[i] in cnt:
        cnt[a[i]] += 1
    else:
        cnt[a[i]] = 1

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

    if c in cnt:
        cnt[c] += b
    else:
        cnt[c] = b

cnts = sorted(cnt.items())
cnt = 0
tot = 0
last = (0, 0)

while cnt < n:
    last = cnts.pop()
    tot += last[0] * last[1]
    cnt += last[1]

tot -= (cnt-n)*last[0]
print(tot)
# Original solution
import heapq

h = []
h2 = []
N, M = [int(i) for i in input().split()]
count = dict()
for i in input().split():
    if not count.get(i):
        count[i] = 0
    count[i] += 1
for k, v in list(count.items()):
    heapq.heappush(h, (int(k), v))

for _ in range(M):
    B, C = [int(i) for i in input().split()]
    heapq.heappush(h2, (C, B))

for i in range(M - 1, -1, -1):
    C, B = h2[i]
    while B > 0:
        if h[0][0] >= C:
            break
        m = h[0][0]
        mc = h[0][1]
        if mc > B:
            heapq.heappush(h, (C, B))
            h[0] = (m, mc - B)
        else:
            heapq.heappop(h)
            heapq.heappush(h, (C, mc))
        B -= mc
print((sum([i[0] * i[1] for i in h])))



# Optimized solution
import heapq

h = []
h2 = []
N, M = [int(i) for i in input().split()]
count = dict()
count2 = dict()
for i in input().split():
    if not count.get(i):
        count[i] = 0
    count[i] += 1
for k, v in list(count.items()):
    heapq.heappush(h, (int(k), v))

for _ in range(M):
    B, C = [int(i) for i in input().split()]
    if not count2.get(C):
        count2[C] = 0
    count2[C] += B
for k, v in list(count2.items()):
    heapq.heappush(h2, (-k, v))
while len(h2) > 0:
    C, B = heapq.heappop(h2)
    C = -C
    while B > 0:
        if h[0][0] >= C:
            break
        m = h[0][0]
        mc = h[0][1]
        if mc > B:
            heapq.heappush(h, (C, B))
            h[0] = (m, mc - B)
        else:
            heapq.heappop(h)
            heapq.heappush(h, (C, mc))
        B -= mc
print((sum([i[0] * i[1] for i in h])))
# Original solution
import sys
input = sys.stdin.readline
n,m = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))
a.sort()
bc=[]
for i in range(m):
    b,c = list(map(int, input().split(" ")))
    bc = bc + [c]*b
bc.sort(reverse=True)
for i in range(n):
    if len(bc) <= i or bc[i] <= a[i]:
        break
    a[i] = bc[i]
print((sum(a)))

# Optimized solution
import sys
input = sys.stdin.readline
n,m = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print((sum(a)))
# Original solution
import sys
input = sys.stdin.readline
n,m = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print((sum(a)))


# Optimized solution
import sys
from itertools import zip_longest
input = sys.stdin.readline
n,m = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        l = l[0:n]
        break
print((sum(list([x[1] if x[0] < x[1] else x[0] for x in zip_longest(a,l,fillvalue=0)]))))
# Original solution
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for i in range(M)]

B = []
C = []

for i in range(M):
    B.append(BC[i][0])
    C.append(BC[i][1])
    
for i in range(M):
    A.sort()
    card = 0
    for j in range(N):
        if A[j] < C[i]:
            A[j] = C[i]
            card += 1
        if card == B[i]:
            break
            
print((sum(A)))

# Optimized solution
from operator import itemgetter

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

BC.sort(key = itemgetter(1),reverse=True)

change = []
for b,c in BC:
    change += [c] * b
    if len(change) > N:
        break
A += change
A.sort(reverse=True)
answer = sum(A[:N])
print(answer)
# Original solution
import bisect

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

a.sort()
l.sort(key=lambda x: x[1], reverse=True)

focus = 0
for b, c in l:
    for j in range(focus, focus+b):
        if j < n: a[j] = max(c, a[j])
    focus += b

print((sum(a)))


# Optimized solution
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())))

a.sort()
l.sort(key=lambda x: x[1], reverse=True)

focus = 0
for b, c in l:
    for j in range(focus, min(focus+b, n)):
        a[j] = max(c, a[j])
    focus += b

print((sum(a)))
# Original solution
import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for i in range(M)],key = lambda x:-x[1])

    cnt = 0
    t = []
    for a,b in tmp:
        t=t+[b]*a
        cnt+= a
        if cnt >=N:
            break

    A = A + t
    A.sort(reverse = 1)
    print((sum(A[:N])))

if __name__ == '__main__':
    sol()


# Optimized solution
import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print((sum(A[:N])))

if __name__ == '__main__':
    sol()
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

# 二次元配列を作る
BC = []
for i in range(M):
    b, c = list(map(int, input().split()))
    BC.append([b, c])

BC = sorted(BC, reverse=True, key=lambda x: x[1])  # Cの値で降順にソートされる

cnt = 0
com = []

for b, c in BC:
    cnt += b
    if cnt > N:  # 操作を加える回数がNを超えることはない
        add = N-cnt+b  # comの要素数の調整
        com.extend([c]*add)
        break
    else:
        com.extend([c]*b)

A.extend(com)

A.sort(reverse=True)
print((sum(A[:N])))


# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
magic = [list(map(int, input().split())) for _ in range(M)]
magic = sorted(magic, key=lambda x: -x[1])

hold = []
now = 0
for k, v in magic:
    hold.extend([v]*k)
    now += k
    if now >= N:
        break
A.extend(hold)
A.sort(reverse=True)
print((sum(A[:N])))
# Original solution
import heapq
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return list(map(int, stdin.readline().split()))
N, M = tuple(li())
A = list(li())
heapq.heapify(A)
def update(pq, k, val):
    # update pq in place
    for _ in range(k):
        cur = heapq.heappop(pq)
        if cur < val:
            heapq.heappush(pq, val)
        else:
            heapq.heappush(pq, cur)
            break

ops = [tuple( li() ) for _ in range(M)]
ops.sort(key=lambda x:x[-1])
for k, val in ops:
    update(A, k, val)

print((sum(A)))


# Optimized solution
import heapq
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return list(map(int, stdin.readline().split()))
N, M = tuple(li())
A = list(li())
heapq.heapify(A)
def update(pq, k, val):
    # update pq in place
    for _ in range(k):
        cur = heapq.heappop(pq)
        if cur < val:
            heapq.heappush(pq, val)
        else:
            heapq.heappush(pq, cur)
            break

ops = []
# val, k_sum
keep = dict()
for i in range(M):
    k, val = tuple(li())
    k_sum = keep.get(val, 0)
    keep[val] = k_sum + k

for val, k in list(keep.items()):
    update(A, k, val)

print((sum(A)))
# Original solution
import heapq
N, M = list(map(int,input().split()))
A = list(map(int,input().split()))
heapq.heapify(A)
for n in range(M):
    B, C = list(map(int,input().split()))
    for b in range(B):
        if C > A[0]:
            heapq.heappushpop(A,C)
        else:
            break
print((sum(A)))



# Optimized solution
import heapq
N, M = list(map(int,input().split()))
A = list(map(int,input().split()))
heapq.heapify(A)
ls_BC = []
for m in range(M):
    ls_BC.append(list(map(int,input().split())))
#print(ls_BC)
ls_BC = sorted(ls_BC, key=lambda x: x[1],reverse=True)
#print(ls_BC)
for B,C in ls_BC:
    for b in range(B):
        if C > A[0]:
            heapq.heappushpop(A,C)
        else:
            break
print((sum(A)))
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
p = [list(map(int, input().split())) for i in range(m)]
cand = sorted(a)
ps = [c for b, c in sorted(p, key = lambda x : x[1], reverse = True) for _ in range(b)]
ans = 0
for candi, psi in zip(cand, ps):
    ans += max(candi, psi)
ans += sum(cand[len(ps):])
print(ans)


# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
p = [list(map(int, input().split())) for i in range(m)]
cand = sorted(a)
ps =  sorted(p, key = lambda x : x[1], reverse = True)
i = 0
ans = 0
def calc():
    global i
    for b, c in ps:
        for d in range(b):
            if i + d == len(cand):
                return sum(cand)
            if cand[i + d] < c:
                cand[i + d] = c
            else:
                return sum(cand)
        i += b
    return sum(cand)
print((calc()))