CodeEff/ECCO huggingface dataset:
# Original solution

def main():

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

    for i in range(M):
        B,C = list(map(int,input().split()))
        tmpList = [C for _ in range(B) ]
        targetList += tmpList
    
    targetList.sort(reverse=True)
    newList = targetList[0:N] if len(targetList) > N else targetList
    A += newList
    A.sort(reverse=True)
    print((sum(A[0:N])))






if __name__== "__main__":
    main() 


# Optimized solution

def main():

    N,M = list(map(int,input().split()))
    A = [i for i in map(int,input().split())]
    A.sort()
    tmpC = 0
    targetList = []

    for i in range(M):

        element = list(map(int,input().split()))
        targetList.append(element)

    targetList.sort(key=lambda x:x[1],reverse=True)
    
    flag = False
    ans = 0
    for b,c in targetList:
        for j in range(b):
            if N > tmpC and A[tmpC] < c:
                ans += c
                tmpC +=1
            else:
                flag = True
                break
        if flag:
            break
    
    if tmpC < N:

        ans += sum(A[tmpC:])


    print(ans)






if __name__== "__main__":
    main()
# Original 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()))
  A.extend([c] * b)
A = sorted(A, reverse=True)
print((sum(A[:N])))

# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = []
for _ in range(M):
  BC.append(list(map(int, input().split())))
BC = sorted(BC, key=lambda x:x[1],reverse=True)  
for b, c in BC:
  A.extend([c] * b)
  if len(A)>=2*N:
    break
A = sorted(A, reverse=True)
print((sum(A[:N])))
# Original solution
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))

A.sort()

#変えられるカードを格納
change_card = []
for _ in range(M):
    B,C = list(map(int,input().split()))
    for _ in range(B):
        change_card.append(C)

change_card.sort()

for i in range(N):
    if max(change_card) > A[i]:
        A[i] = max(change_card)
        change_card[change_card.index(max(change_card))] = -1

print((sum(A)))

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

A.sort()

BC = [list(map(int,input().split())) for _ in range(M)]
#変えられるカードを格納
BC_sort = sorted(BC,key=lambda x: x[1])

BC_sort_index = M-1

for i in range(N):
    if BC_sort[BC_sort_index][1] > A[i]:
        A[i] = BC_sort[BC_sort_index][1]
        BC_sort[BC_sort_index][0] -= 1
        if BC_sort[BC_sort_index][0] == 0:
            BC_sort_index -= 1
            if BC_sort_index < 0:
                break

print((sum(A)))
# Original solution
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]

P = sorted(([[1,A[i]] for i in range(N)] + L),key=lambda x: x[1],reverse=True)

ans = 0
rest = N

for cost,value in P :
    K = min(cost, rest)
    K = max(0,K)
    ans += K * value
    rest -= cost

print(ans)


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

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

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

for i in range(N) :
    L.append([1,A[i]])

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

ans = 0

for i in range(len(L)) :
    number, point = L[i]
    
    if number > N :
        number = N
    
    ans += number * point
    N -= number
    
print(ans)
# Original solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
bc = [[0]*2]*m
for i in range(m):
  bc[i] = list(map(int,input().split()))
  
std = sorted(bc, key=lambda x: x[1], reverse=True)
  
for i in range(m):
  if min(a) >= std[i][1]:
    break
  for j in range(std[i][0]):
    a[a.index(min(a))] = max(std[i][1], min(a))

print((sum(a)))


# Optimized solution
#5618213
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
  
for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break
a.sort(reverse=True)
print((sum(a[:n])))
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
addable = []
for m in range(M):
    B, C = list(map(int, input().split()))
    addable += [C] * B

addable.sort()
addable = addable[-len(A):]
NA = A + addable
NA.sort()
print((sum(NA[-len(A):])))


# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
p = [(A[i], 1) for i in range(N)]
for m in range(M):
    B, C = list(map(int, input().split()))
    p.append((C, B))

p.sort()
p.reverse()

ans = 0
for v, n in p:
    use = min(N, n)
    ans += use * v
    N -= use
    if N == 0:
        break
print(ans)
# Original solution
N, M = list(map(int, input().split()))
A_array = list(map(int, input().split()))
BC_array = [list(map(int, input().split())) for _ in range(M)]
BC_array = sorted(BC_array, key=lambda x: -x[1])
B_count = 0
for B, C in BC_array:
    A_array = A_array + [C] * B
    B_count += B
    if B_count >= N:
        break
A_array.sort()
# print(A_array)
print((sum(A_array[-N:])))

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

plus_count = 0
ans = 0
a_index = N - 1
bc_index = M - 1

while plus_count != N:
    if A_array[a_index] <= BC_array[bc_index][1]:
        add_count = min(BC_array[bc_index][0], N - plus_count)
        plus_count += add_count
        ans += (add_count * BC_array[bc_index][1])
        bc_index -= 1
        if bc_index < 0:
            a_rest = N - plus_count
            ans += sum(A_array[a_index - a_rest + 1:a_index + 1])
            break
    else:
        plus_count += 1
        ans += A_array[a_index]
        a_index -= 1
print(ans)
# Original solution
N, M = list(map(int,input().split()))
A = list(map(int,input().split()))

res = []
for _ in range(M):
  B, C = list(map(int,input().split()))
  res += [C]*B

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

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

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print((sum(A[:N])))
# Original solution
from heapq import heapify, heappush, heappop


(N, M), *AB = [list(map(int, s.split())) for s in open(0)]
A = AB[0]
heapify(A)
for b, c in AB[1:]:
    while b > 0 and c > A[0]:
        a = heappop(A)
        heappush(A, c)
        b -= 1
print((sum(A)))

# Optimized solution
(N, M), *AB = [list(map(int, s.split())) for s in open(0)]
A = sorted(AB[0])
D = []
for b, c in sorted(AB[1:], key=lambda x: (-x[1], x[0])):
    D.extend([c] * b)
    if len(D) >= N:
        D = D[:N]
        break
D = D[::-1]
for i in range(N):
    if not D or D[-1] <= A[i]:
        break
    A[i] = D.pop()

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

n, m = list(map(int, input().split()))
ls = sorted(map(int, input().split()))
ls2 = [list(map(int, input().split())) for _ in range(m)]
ls2.sort(key=lambda x: (x[1], x[0]), reverse=True)
left = 0
res = 0
for b, c in ls2:
    if left == n or c <= ls[left]:
        break
    i = bisect.bisect(ls[left:], c)
    i = min(i, b)
    res += c * i
    left += i
print((res + sum(ls[left:])))

# Optimized solution
n, m = list(map(int, input().split()))
ls = sorted(map(int, input().split()))
ls2 = [list(map(int, input().split())) for _ in range(m)]
ls2.sort(key=lambda x: (x[1], x[0]), reverse=True)
left = 0
right = 0
index = 0
res = 0
while left < n:
    if index == len(ls2):
        break
    b, c = ls2[index]
    if c <= ls[left]:
        break
    right = left + 1
    while right <= n:
        if right == n:
            res += c * (right - left)
            break
        if ls[right] <= c and right - left < b:
            right += 1
        else:
            res += c * (right - left)
            break
    left = right
    index += 1

print((res + sum(ls[left:])))
# Original solution
import heapq


def main():
    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):
            heapq.heappushpop(A, C)
    print((sum(A)))


if __name__ == '__main__':
    main()

# Optimized solution
def main():
    N, M = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    updates = list()
    for _ in range(M):
        B, C = list(map(int, input().split(' ')))
        updates.append((B, C))
    updates.sort(key=lambda x: x[1], reverse=True)
    for B, C in updates:
        A.extend([C] * B)
        if len(A) > 2 * N:
            break
    A.sort(reverse=True)
    print((sum(A[:N])))


if __name__ == '__main__':
    main()
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(key=lambda x: x[1], reverse=True)
d = []
i = 0

while len(d) <= n and i < len(bc):
    d += ([bc[i][1]] * bc[i][0])
    i += 1

if len(d) > n:
    d = d[:n]

sum_max = sum(a)
for x in range(len(d)):
    a[x] = d[x]
    sum_a = sum(a)
    if sum_a > sum_max:
        sum_max = sum_a

print(sum_max)


# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

bc.sort(key=lambda x: x[1], reverse=True)
d = []
i = 0

while len(d) <= n and i < len(bc):
    d += ([bc[i][1]] * bc[i][0])
    i += 1

if len(d) > n:
    d = d[:n]

a += d
a.sort(reverse=True)

print((sum(a[:n])))
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

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

i = 0
for b, c in bc:
    for _ in range(b):
        if i < n and a[i] < c:
            a[i] = c
            i += 1
        else:
            break

ans = sum(a)
print(ans)


# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

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

li = []
l = 0
i = 0
while i < m and l < n:
    b, c = bc[i]
    li += [c] * b
    i += 1
    l += b

a += li
a.sort(reverse=True)
ans = sum(a[:n])
print(ans)
# Original solution
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
A.sort()
BC = []
for _ in range(M):
    BC.append(inpl())
BC.sort(key=lambda x: -x[1])
t = 0
S = 0
for B,C in BC:
    f = t
    t = f + B
    if t > N:
        t = N
    if f >= N:
        break
    if C >= A[t-1]:
        S += (t-f)*C
    else:
        for i in range(f,t):
            if C >= A[i]:
                S += C
            else:
                t = i
                break
        break
if t < N:
    S += sum(A[t:])
print(S)

# Optimized solution
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
A.sort()
BC = []
for _ in range(M):
    BC.append(inpl())
BC.sort(key=lambda x: -x[1])
 
D = []
for B, C in BC:
    if len(D) >= N:
        break
    d = [int(C)]*B
    D += d
D.sort(reverse=True)

lenD = len(D)
if lenD > N:
    lenD = N

for i in range(lenD):
    if D[i] > A[i]:
        A[i] = D[i]
    else:
        break
ans = sum(A)
print(ans)
# Original solution
N, M = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
for _ in range(M):
    B, C = list(map(int, input().split(' ')))
    A.extend([C]*B)
print((sum(sorted(A)[-N:])))

# Optimized solution
N, M = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
for _ in range(M):
    B, C = list(map(int, input().split(' ')))
    A.extend([C]*B)
    A = sorted(A)[-N:]
print((sum(A)))
# Original solution
N, M = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
for _ in range(M):
    B, C = list(map(int, input().split(' ')))
    A.extend([C]*B)
    A = sorted(A)[-N:]
print((sum(A)))

# Optimized solution
N, M = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
BC_list = []
for _ in range(M):
    B, C = list(map(int, input().split(' ')))
    BC_list.append((B, C))
BC_list = sorted(BC_list, key= lambda x: x[1], reverse=True)

for b, c in BC_list:
    A.extend([c]*b)
    if len(A) > 2*N:
        break
print((sum(sorted(A)[-N:])))
# Original solution
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(eval(input()))
def FLOAT(): return float(eval(input()))
MOD = 10**9+7


n,m = MAP()
a = MAP()
heapify(a)
d = []
for i in range(m):
    b,c = MAP()
    d += [c]*b

d.sort(reverse=True)

while 1:
    tmp = heappop(a)
    if tmp<d[0]:
        heappush(a,d.pop(0))
    else:
        a+=[tmp]
        break
    if len(d)==0:
        break

print((sum(a)))

# Optimized solution
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(eval(input()))
def FLOAT(): return float(eval(input()))
MOD = 10**9+7


n, m = MAP()
a = MAP()
p = [(a[i], 1) for i in range(n)]
for j in range(m):
    b, c = MAP()
    p.append((c, b))
p.sort(reverse=True)
ans, cnt = 0, n
for (v, c) in p:
    use = min(c, cnt)
    ans += use * v
    cnt -= use
print(ans)
# Original solution
from heapq import (
    heapify,  # 優先度付きキューの生成
    heappop,  # キューから値を取り出す
    heappush,   # キューに値を格納
    heappushpop,   # push -> popの順
    heapreplace,   # pop -> pushの順
    )

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

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

A = A + bc
heapify(A)
total = 0

for _ in range(N):
    total += -heappop(A)

print(total)

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

dic = {}
for i in range(N):
    tmp = A[i]
    if tmp in dic:
        dic[tmp] += 1
    else:
        dic[tmp] = 1

for _ in range(M):
    B, C = list(map(int, input().split()))
    if C in dic:
        dic[C] += B
    else:
        dic[C] = B

dic = sorted(list(dic.items()), reverse=True)

ans, cnt = 0, 0
i = 0
while True:
    k, v = dic[i]
    cnt += v
    if cnt < N:
        ans += k*v
    elif cnt == N:
        ans += k*v
        break
    else:
        ans += k*(v - (cnt-N))
        break
    i += 1

print(ans)
# Original solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for _ in range(m)]

bc = sorted(bc,key=lambda x:(x[1]))
count=0
for b,c in bc:
  count += b
  a.extend([c]*b)
  if b > n:
    break
    
print((sum(sorted(a,reverse=True)[:n])))

# Optimized solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for _ in range(m)]

bc = sorted(bc,key=lambda x:(x[1]),reverse=True)
count=0
for b,c in bc:
  count += b
  a.extend([c]*b)
  if count >= n:
    break
    
print((sum(sorted(a,reverse=True)[:n])))
# Original solution
import sys
import heapq
input = sys.stdin.readline

n,m = list(map(int,input().split()))
heap = [int(i) for i in input().split()]
heap.sort()

for i in range(m):
  a,b = list(map(int,input().split()))
  for j in range(a):
    if heap[0] < b:
      heapq.heappop(heap)
      heapq.heappush(heap,b)
      
print((sum(heap)))

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

n,m = list(map(int,input().split()))
heap = [int(i) for i in input().split()]
heap.sort()
ans = sum(heap)
ml = []
cnt = 0

for i in range(m):
  a,b = list(map(int,input().split()))
  ml += [[b,a]]
ml.sort(reverse=True)

for i in range(m):
  for j in range(ml[i][1]):
    if ml[i][0] > heap[cnt]:
      ans += ml[i][0] - heap[cnt]
      cnt += 1
      if cnt == n:
        print(ans)
        exit()
    else:
      print(ans)
      exit()
print(ans)
# Original solution
import sys
def input():
    return sys.stdin.readline()[:-1]


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

BC_list = []

for i in range(M):
    B, C = list(map(int, input().split()))

    BC_list.append({
        'B': B,
        'C': C
    })


BC_list.sort(reverse=True, key=lambda x: x['C'])

A_last = min(A)

for pair in BC_list:

    if pair['C'] < A_last:
        break

    for _ in range(pair['B']):
        A.append(pair['C'])

A.sort(reverse=True)

print((sum(A[0:N])))


# Optimized solution
import sys
def input():
    return sys.stdin.readline()[:-1]


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

BC_list = []

for i in range(M):
    B, C = list(map(int, input().split()))

    BC_list.append({
        'B': B,
        'C': C
    })

BC_list.sort(reverse=True, key=lambda x: x['C'])

A_last = min(A)

limit_count = 0

for pair in BC_list:

    if pair['C'] < A_last:
        break

    for _ in range(pair['B']):
        A.append(pair['C'])

    limit_count += pair['B']
    if limit_count > N:
        break

A.sort(reverse=True)

print((sum(A[0:N])))
# Original solution
from collections import deque
n,m=list(map(int,input().split()))
A=sorted(list(map(int,input().split())))
BC=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])

A=deque(A)
for b,c in BC[::-1]:
    if len(A)==0:break
    for i in range(b):
        if A[0]<c:
            A.append(c)
            A.popleft()
        else:break
print((sum(A)))

# Optimized solution
from collections import deque
n,m=list(map(int,input().split()))
A=sorted(list(map(int,input().split())))
BC=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])

A=deque(A)
for b,c in BC[::-1]:
    for i in range(b):
        if A[0]<c:
            A.append(c)
            A.popleft()
        else:break
print((sum(A)))
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [[c]*b for b, c in [list(map(int, input().split())) for _ in range(M)]]

R=sum(BC,[])
T=sorted(A+R,reverse=True)
print((sum(T[:len(A)])))



# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [[c]*b for b, c in [list(map(int, input().split())) for _ in range(M)]]

R=sum(BC,[])
if len(R)>len(A):
    R=sorted(R,reverse=True)[:len(A)]
T=sorted(A+R,reverse=True)
print((sum(T[:len(A)])))
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [[c]*b for b, c in [list(map(int, input().split())) for _ in range(M)]]

R=sum(BC,[])
if len(R)>len(A):
    R=sorted(R,reverse=True)[:len(A)]
T=sorted(A+R,reverse=True)
print((sum(T[:len(A)])))



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

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

R=[]
n=0
for i in BC:
    R = R+[i[1]]*i[0]
    n = n + i[0]
    if n >= N:
        break

R=sorted(A+R, reverse=True)[:N]
print((sum(R)))
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

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

R=[]
n=0
for i in BC:
    R = R+[i[1]]*i[0]
    n = n + i[0]
    if n >= N:
        break

R=sorted(A+R, reverse=True)[:N]
print((sum(R)))



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

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

R=[]
n=0
for i in range(M):
    R.extend([BC[i][1]]*BC[i][0])
    n = n + BC[i][0]
    if n >= N:
        break

R=sorted(A+R, reverse=True)[:N]
print((sum(R)))
# Original solution
n, m = tuple(map(int, input().split()))
x = sorted(list(map(int, input().split())))
y = [tuple(map(int, input().split())) for i in range(m)]
for b,c in y:
  while x[b-1] > c and b > 0:
    b -= 1
  x[0:b] = [c]*b
  x.sort()
print((sum(x)))

# Optimized solution
n, m = tuple(map(int, input().split()))
x = sorted(list(map(int, input().split())))
y = [list(map(int, input().split())) for i in range(m)]
y.sort(key = lambda x: x[1], reverse=True)
y_pos = 0
for index, value in enumerate(x):
  b = y[y_pos][0]
  c = y[y_pos][1]
  if value < c:
	  x[index] = c
	  y[y_pos][0] = b-1
	  if b == 1:
		  y_pos += 1
		  if y_pos == len(y):
			  break
  else:
	  break

print((sum(x)))
# Original solution
n,m=list(map(int,input().split()))
*a,=list(map(int,input().split()))
l=[list(map(int,input().split()))[::-1] for _ in range(m)]
a.sort()
d=[]
e=0
for c,b in sorted(l)[::-1]:
	d+=[c]*b
	e+=b
	if e>n:break
for i,(x,y) in enumerate(zip(a,d)):
	if x<y:a[i]=y
print((sum(a)))


# Optimized solution
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
Z=[list(map(int,input().split()))[::-1] for _ in range(m)]
d=[]
e=0
a.sort()
Z.sort(reverse=True)
for c,b in Z:
    d+=[c]*b
    e+=b
    if e>n:
        break

for i , (x,y) in enumerate(zip(a,d)):
    if x<y:
        a[i]=y

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


def main():
    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):
            n = heapq.heappop(A)
            if n<c:
                heapq.heappush(A, c)
            else:
                heapq.heappush(A, n)
                break
    
    print((sum(A)))
        


if __name__ == '__main__':
    main()

# Optimized solution
import heapq
import sys
input = sys.stdin.readline
 
 
def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    heapq.heapify(A)
 
    BC = []
    for _ in range(M):
        b, c = list(map(int, input().split()))
        BC.append([c*(-1), b])
    heapq.heapify(BC)
    
    flg = True
    while flg:
        if len(BC)==0:
            break
        c, b = heapq.heappop(BC)
        c *= -1
        for _ in range(b):
            a = heapq.heappop(A)
            if a<c:
                heapq.heappush(A, c)
            else:
                heapq.heappush(A, a)
                flg = False
                break

    print((sum(A)))
        
 
 
if __name__ == '__main__':
    main()
# Original solution
import heapq

N, M = list(map(int, input().split()))
A_LIST = list(map(int, input().split()))
BC_LIST = []
heapq.heapify(A_LIST)
for i in range(M):
    b, c = list(map(int, input().split()))
    BC_LIST.append([b, c])
BC_LIST.sort(reverse=True, key=lambda x: x[1])  # C降順にソート
for b, c in BC_LIST:
    for _ in range(b):
        tmp = heapq.heappop(A_LIST)
        if tmp < c:
            heapq.heappush(A_LIST, c)
        else:
            heapq.heappush(A_LIST, tmp)
            break
print((sum(A_LIST)))


# Optimized solution
N, M = list(map(int, input().split()))
A_LIST = list(map(int, input().split()))
BC_LIST = []
for i in range(M):
    b, c = list(map(int, input().split()))
    BC_LIST.append([b, c])
card_dict = {}
for a in A_LIST:
    if a in card_dict:
        card_dict[a] += 1
    else:
        card_dict[a] = 1
for b, c in BC_LIST:
    if c in card_dict:
        card_dict[c] += b
    else:
        card_dict[c] = b
card_list = sorted(list(card_dict.items()), reverse=True, key=lambda x: x[0])
ans = 0
remaining = N
for num, cnt in card_list:
    ans += num * min(cnt, remaining)
    remaining -= min(cnt, remaining)
    if remaining == 0:
        break
print(ans)