CodeEff/ECCO huggingface dataset:
# Original solution
import heapq
N,M = list(map(int,input().split(' ')))
An = list(map(int,input().split(' ')))
heapq.heapify(An)
BC_list = []
for i in range(M):
    BC = list(map(int,input().split(' ')))
    BC_list.append(BC)
BC_list.sort(reverse=True,key=lambda x: x[1])
flag = False
for val in BC_list:
    B = val[0]
    C = val[1]
    for i in range(B):
        tmp_min = heapq.heappop(An)
        if tmp_min > C:
            heapq.heappush(An,tmp_min)
            flag = True
            break
        heapq.heappush(An,C)
    if flag:
        break
print((sum(An)))

# Optimized solution
import heapq
N,M = list(map(int,input().split(' ')))
An = list(map(int,input().split(' ')))
heapq.heapify(An)
BC_list = []
for i in range(M):
    BC = list(map(int,input().split(' ')))
    BC_list.append(BC)
BC_list.sort(reverse=True,key=lambda x: x[1])
flag = False
decided_sum = []
for val in BC_list:
    B = val[0]
    C = val[1]
    for i in range(B):
        tmp_min = heapq.heappop(An)
        if tmp_min > C:
            #heapq.heappush(An,tmp_min)
            decided_sum.append(tmp_min)
            flag = True
            break
        decided_sum.append(C)
        if len(An) == 0:
            flag = True
            break
    if flag:
        break
print((sum(decided_sum) + sum(An)))
# Original solution
from collections import defaultdict
N, M=list(map(int, input().split()))
A=list(map(int, input().split()))
d=defaultdict(int)
for a in A:
  d[a]+=1
for i in range(M):
  B, C=list(map(int, input().split()))
  d[C]+=B
index_list=sorted(d)
ans=0
ans_size=0
for i in range(len(index_list)-1, -1, -1):
  card=index_list[i]
  if d[card]+ans_size>=N:
    ans+=(N-ans_size)*card
    break
  else:
    ans+=d[card]*card
    ans_size+=d[card]
print(ans)

# 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.sort(key=lambda x:(x[1], x[0]), reverse=True)

for b, c in BC:
    if len(A) and A[0]>=c:
        break
    for i in range(b):
        if len(A) and A[0]>=c:
            break
        heapq.heappop(A)
        heapq.heappush(A, c)

print((sum(A)))
# Original solution
import bisect
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()))
    if C >= A[0]:
        if C >= A[B-1]:
            if C >= A[N-1]:
                A = A[B:] + [C]*B
            else:
                x = bisect.bisect(A[B:], C)
                A = A[B:B+x] + [C]*B + A[B+x:]
        else:
            x = bisect.bisect(A[:B], C)
            A = [C]*x + A[x:]
print((sum(A)))

# Optimized solution
N, M = list(map(int, input().split()))
A = sorted(map(int, input().split()))
BC = sorted((tuple(map(int, input().split())) for _ in range(M)), key=lambda x:x[1])
D = []
x = 0
for i in range(M-1,-1,-1):
    if x + BC[i][0] >= N:
        D += [BC[i][1]]*(N-x)
        break
    D += [BC[i][1]]*BC[i][0]
    x += BC[i][0]
for i in range(len(D)):
    if A[i] >= D[i]:
        break
    A[i] = D[i]
print((sum(A)))
# Original solution
from heapq import heappush, heappop
N,M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(M)]
result = 0

hq = []
for j in A:
    heappush(hq, (-j))

for i in e:
    for n in range(i[0]):
        heappush(hq, (-i[1]))

A.sort(reverse=True)
for k in range(N):
    result += heappop(hq) * -1

print(result)

# Optimized solution
import bisect
N,M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(M)]
result = 0
hoge = min(A)
A.sort()

for i in e:
    hoge = bisect.bisect_left(A,i[1])
    for j in range(i[0]):
        A.insert(hoge,i[1])
        A.pop(0)


for k in range(N):
    result += A[ N - k - 1]

print(result)
# Original solution
import sys

N, M = list(map(int, sys.stdin.readline().split()))
a_list = list(map(int, sys.stdin.readline().split()))
items = []
for i in range(M):
    items.append(tuple(map(int, sys.stdin.readline().split())))


from collections import defaultdict

tar = defaultdict(int)
for a in a_list:
    tar[a] += 1

for i in range(M):
    b, c = items[i]
    tar[c] += b

tar = sorted(list(tar.items()), key=lambda x: -x[0])

cnt = 0
ans = 0
for k, v in tar:
    if cnt + v <= N:
        cnt +=v
        ans += k*v
    else:
        ans += k*(N-cnt)
        cnt = N
    if cnt >= N:
        break
print(ans)


# Optimized solution
import sys

N, M = list(map(int, sys.stdin.readline().split()))
a_list = list(map(int, sys.stdin.readline().split()))
items = []
for i in range(M):
    items.append(tuple(map(int, sys.stdin.readline().split())))

from heapq import *

que = []

for i in range(N):
    a = a_list[i]
    heappush(que, (-a, 1))

for b, c in items:
    heappush(que, (-c, b))

cnt = 0
ans = 0
while cnt < N:
    k, v = heappop(que)
    if cnt + v <= N:
        cnt += v
        ans += -(k * v)
    else:
        ans += -(k) * (N-cnt)
        cnt = N
print(ans)
# Original solution
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))
a = [int(_) for _ in input().split()]
cb = [0] * m
for i in range(m):
    bb, cc = list(map(int, input().split()))
    cb[i] = (cc, bb)

cb.sort(reverse=True)

arr = []
l = 0
for i in range(m):
    if l + cb[i][1] > 10**5:
        add = 10**5 - l
        for j in range(add):
            arr.append(cb[i][0])
        break
    else:
        for j in range(cb[i][1]):
            arr.append(cb[i][0])

a = a + arr
a.sort(reverse=True)
print((sum(a[0:n])))

# Optimized solution
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))
a = [int(_) for _ in input().split()]
cb = [0] * m
for i in range(m):
    bb, cc = list(map(int, input().split()))
    cb[i] = (cc, bb)

cb.sort(reverse=True)

arr = []
l = 0
for i in range(m):
    if l + cb[i][1] > 10**5:
        add = 10**5 - l
        for j in range(add):
            arr.append(cb[i][0])
        break
    else:
        for j in range(cb[i][1]):
            arr.append(cb[i][0])
        l += cb[i][1]

a = a + arr
a.sort(reverse=True)
print((sum(a[0:n])))
# Original solution
N,M = [int(x) for x in input().split()]

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

# print(A)
print((sum(A)))


# Optimized solution
N,M = [int(x) for x in input().split()]

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)
    if(len(str) > N):
        break

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

# print(A)
print((sum(A)))
# 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)]
ans = []
A.sort()
count = 0
for b,c in BC:
    ans += [c]*b
ans.extend(A)
ans = sorted(ans,reverse = True)
print((sum(ans[:N])))

# Optimized solution
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
BC = [(A[i], 1) for i in range(N)]
for _ in range(M):
    B, C = list(map(int, input().split()))
    BC.append((C,B))
BC = sorted(BC,reverse = True)
ans = 0
a = 0
count = N
for c,b in BC:
  lamb = min(count,b)
  ans += c * lamb
  count -= lamb

print(ans)
# Original solution
n,m=list(map(int,input().split()))
from collections import deque
que=deque(list(map(int,input().split())))
for _ in range(m):
    b,c=list(map(int,input().split()))
    que=sorted(que)
    for i in range(b):
        if que[0]<c:
            que.pop(0)
            que.append(c)
        else:
            break

print((sum(que)))


# Optimized solution
n,m=list(map(int,input().split()))
List=sorted(list(map(int,input().split())))
s=[]
for _ in range(m):
    s.append(list(map(int,input().split())))
s.sort(key=lambda x: x[1], reverse=True)

ans=0
j=0
for i in range(m):
    if j>=n or s[i][1]<=List[j]:
        break
    while j<n and s[i][0]>0 and s[i][1]> List[j]:
        ans+=s[i][1]
        s[i][0]-=1
        j+=1
if j>=n:
    print(ans)
else:
    print((ans+sum(List[j:])))
# Original solution
import bisect

n, m = list(map(int, input().split()))
arr = list(sorted(list(map(int, input().split()))))
bc = []
for _ in range(m):
    b, c = list(map(int, input().split()))
    bc.append([b, c])

bc = list(sorted(bc, key=lambda x: x[1], reverse=True))
ans = 0

for bci in bc:
    d = bisect.bisect_left(arr, bci[1])
    arr = arr[min(d, bci[0]) :]
    ans += min(d, bci[0]) * bci[1]
print((ans + sum(arr)))


# Optimized solution
# 書き換える枚数は確定できる
# cの大きい順にしたものでaの小さい順にしたものを置き換えるイメージ
# なんか尺取っぽくなった

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

bcs = []
for _ in range(m):
    bc = list(map(int, input().split()))
    bcs.append(bc)

bcs = sorted(bcs, key=lambda x: x[1], reverse=True)
ans = 0

i = 0
for b in bcs:
    while i < n and arr[i] < b[1] and b[0] > 0:
        ans += b[1]
        b[0] -= 1
        i += 1
print((ans + sum(arr[i:])))
# Original solution
from bisect import bisect
N, M = list(map(int, input().split()))
A = sorted([int(i) for i in input().split()])
BC = [[int(i) for i in input().split()] for i in range(M)]
BC = sorted(BC, key=lambda x:-x[1])
ans = 0
for b, c in BC:
    i = bisect(A, c)
    i = min(i, b)
    A = A[i:]
    ans += c * i
print((ans+sum(A)))

# Optimized solution
from bisect import bisect
N, M = list(map(int, input().split()))
A = sorted([int(i) for i in input().split()])
BC = [[int(i) for i in input().split()] for i in range(M)]
BC = sorted(BC, key=lambda x:-x[1])
ans = 0
offset=0

for b, c in BC:
    i = bisect(A, c, lo=offset)
    i = min(i-offset, b)
    ans += c * i
    offset += i

print((ans+sum(A[offset:])))
# 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()))
    count = 0
    while count < b:
        a.append(c)
        count += 1
a.sort(reverse=True)
print((sum(a[:n])))

# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
l = []
for i in range(m):
    b, c = list(map(int, input().split()))
    l.append((b, c))
for i in a:
    l.append((1, i))
l.sort(key=lambda x: x[1], reverse=True)
#print(l)
count = n
ans = 0
for item in l:
    b, c = item
    ans += c*min(b, count)
    count -= b
    if count <= 0:
        break
print(ans)
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
b = []
for i in range(M):
    b.append(list(map(int, input().split())))
A.sort()
b.sort(key=lambda x: x[1], reverse= True)
for i in range(M):
    for j in range(b[i][0]):
        if A[j] < b[i][1]:
            A[j] = b[i][1]
        else:
            break
    A.sort()
print((sum(A)))

# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
b = []
for i in range(M):
    b.append(list(map(int, input().split())))
ans = 0
A.sort()
b.sort(key=lambda x: x[1], reverse=True)
j = 0
for i in range(M):
    if j >= N or b[i][1] <= A[j]:
        break
    while j < N and b[i][0] and b[i][1] > A[j]:
        ans += b[i][1]
        b[i][0] -= 1
        j += 1
if j >= N:
    print(ans)
else:
    print((ans + sum(A[j:])))
# 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 = sorted(a + [c] * b, reverse=True)[:n]

print((sum(a)))

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

bc = [tuple(map(int, input().split())) for _ in range(m)]
a.sort()
bc.sort(key=lambda x:x[1], reverse=True)

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

if idx < n:
    res += sum(a[idx:])

print(res)
# Original solution
import heapq

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 i in range(b):
        if A[0] < c:
            heapq.heappop(A)
            heapq.heappush(A, c)
        else:
            break
print((sum(A)))


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

A.sort()
D.sort(key=lambda x:x[1], reverse=True)
NewCard = []
for d in D:
    b, c = d
    NewCard += [c] * b
    if(len(NewCard) > N):
        break

i = 0
len_min = min(len(A), len(NewCard))
while i < len_min:
    if A[i] >= NewCard[i]:
        break
    i += 1

print((sum(NewCard[:i]) + sum(A[i:])))
# Original solution
from bisect import bisect_left
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)
A.sort()
bisec = bisect_left
ex = A.extend
for i in range(M):
    if BC[i][1]<A[0]:
        break
    B= BC[i][0]
    C = BC[i][1]
    b = bisec(A,C)
    if B>=b:
        ex([C for _ in range(b)])
        del A[:b]
    else:
        ex([C for _ in range(B)])
        del A[:B]
print((sum(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 = sorted(BC,key= lambda x: x[1],reverse=True)
A.sort()
n = 0
i = 0
m = 0
while A[i]<BC[n][1]:
    A[i] = BC[n][1]
    m = m+1
    if m >=BC[n][0]:
        m = 0
        n = n+1
    i += 1
    if n==M:
      break
    if i == N:
      break
print((sum(A)))
# Original solution
import bisect

N, M = list(map(int, input().split()))
A_list = sorted( list( int(i) for i in input().split() ))
BC_list = sorted(
  list( list( int(i) for i in input().split() ) for _ in range(M) ),
  key=lambda x:-x[1]
)

n = N
for bc in BC_list:
  for i in range(bc[0]):
    if bisect.bisect_right(A_list, bc[1]) < len(A_list) - N :
      pass
    bisect.insort_right(A_list, bc[1])
L = len(A_list)
print((sum(A_list[L:L-N-1:-1])))

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

change_list = []
for bc in BC_list:
  change_list += [bc[1]] *  bc[0]
  if len(change_list) >= N :
    break
A_list += change_list
A_list.sort()
L = len(A_list)
print((sum(A_list[L:L-N-1:-1])))
# Original solution
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
l=[]
for i in range(m):
    b,c=list(map(int,input().split()))
    l+=[c]*b
l.sort()
l=l[::-1]
ans=0
#print(a,l)
for i in range(n):
    if i<=len(l)-1:
        ans+=max(a[i],l[i])
    else:
        ans+=a[i]

print(ans)

# Optimized solution
import sys
imput=sys.stdin.readline
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
l=[]
for i in range(m):
    b,c=list(map(int,input().split()))
    l+=[c]*b
l.sort()
l=l[::-1]
ans=0
#print(a,l)
for i in range(n):
    if i<=len(l)-1:
        ans+=max(a[i],l[i])
    else:
        ans+=a[i]

print(ans)
# 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 A[0] < C:
            heapq.heapreplace(A, C)
        else:
            break

ans = sum(A)
print(ans)


# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
p = [[A[i], 1] for i in range(N)]   # Aのカードは各1枚ずつ

for i in range(M):
    B, C = list(map(int, input().split()))
    p.append([C, B])    # CのカードをB枚追加

p.sort()
p.reverse()

ans = 0
cnt = N
for v, n in p:
    num = min(cnt, n)    # 残り枚数とvのカード枚数の少ない方を採用
    ans += v * num
    cnt -= num
    if cnt == 0:
        break

print(ans)
# Original solution
import heapq

n,m=list(map(int,input().split()))
a=sorted(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):
    tmp=heapq.heappop(a)
    if tmp<c:
      heapq.heappush(a,c)
    else:
      heapq.heappush(a,tmp)
      break
print((sum(a)))

# Optimized solution
import heapq

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

li=[list(map(int,input().split())) for i in range(m)]
li=sorted(li,key=lambda x:x[1],reverse=True)
for i in range(m):
  tmp=heapq.heappop(a)
  if tmp>li[i][1]:
    heapq.heappush(a,tmp)
    break
  else:
    heapq.heappush(a,tmp)
    for j in range(li[i][0]):
      tmp=heapq.heappop(a)
      if tmp<li[i][1]:
        heapq.heappush(a,li[i][1])
      else:
        heapq.heappush(a,tmp)
        break
print((sum(a)))
# Original solution
import collections

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
cnt = 0
s = 0
for _ in range(m):
    b, c = list(map(int, input().split()))
    a += [c] * b

ca = collections.Counter(a)
cas = sorted(list(ca.items()), key=lambda x: -x[0])
for i in range(n):
    if n > cnt + cas[i][1]:
        s += cas[i][0] * cas[i][1]
        cnt += cas[i][1]
    else:
        s += cas[i][0] * (n - cnt)
        break

print(s)

# 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(reverse=True, 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 = i+b
print((sum(a)))
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x: -x[1])
# print(a)
# print(bc)

count = 0
end = False
for b, c in bc:
  if end:
    break
  if len(a) <= 0:
    break
  for j in range(b):
    if end:
      break
    if a[0] < c:
      count += c
      # print(c)
      del a[0]
    else:
      end = True

print((count + sum(a)))


# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x: -x[1])
# print(a)
# print(bc)

count = 0
idx = -1
end = False
for b, c in bc:
  if idx + b <= n-1 and a[idx+b] < c:
    count += b * c
    idx += b
  else:
    for i in range(idx+1, idx+1+b):
      if i >= n or end:
        break
      else:
        if a[i] < c:
          count += c
          idx += 1
        else:
          end = True
  # print((idx, count))
  if end:
    break

if idx <= n-2:
  count += sum(a[idx+1:])

print(count)
# Original solution
n,m=list(map(int,input().split()))
*q, = list(map(int,input().split()))
#print(q)
l = []
for _ in range(m):
  b,c = list(map(int,input().split()))
  for i in range(b):
    l.append(c)
li = q+l
print((sum(sorted(li,reverse=True)[:n])))

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

print((sum(sorted(q,reverse=True)[:n])))
# Original solution
n,m = list(map(int,input().split()))
*q, = list(map(int,input().split()))
l = []
for _ in range(m):
  b, c = list(map(int,input().split()))
  l.extend([c]*b)
#print(l)
l.sort(reverse=True)
for i in l:
  q.extend([i])
  if len(q) > 2*n:
    break
q.sort(reverse=True)
print((sum(q[:n])))

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

N, M = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
A.sort()

for i in range(M):
    b, c = [int(_) for _ in input().split()]
    cnt = 0
    for j in range(b):
        if len(A) <= j: break
        if A[j] >= c: break
        cnt += 1
    if cnt > 0:
        # A = A[cnt:]
        idx = bisect.bisect_left(A, c)
        A = A[cnt:idx] + ([c] * cnt) + A[idx:]
        # print(A)

print((sum(A)))

# Optimized solution
N, M = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
A.sort()

BC = []
for i in range(M):
    v = [v for v in input().split()]
    BC.append((int(v[0]), int(v[1])))

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

i = 0

fin = False
for b, c in BC:
    for _ in range(b):
        if i >= N:
            fin = True
            break

        if A[i] < c:
            A[i] = c
            i += 1
        else:
            fin = True
            break
    if fin:
        break
print((sum(A)))
# Original solution
n,m = list(map(int,input().split()))
cards = list(map(int,input().split()))

from collections import deque

cards = deque(cards)

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

    cards+=[c]*b

cards = sorted(cards,reverse=True)

total = 0
for i in range(n):
    total += cards[i]

print(total)


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

import heapq

heapq.heapify(cards)

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

    for _ in range(b):
        heapq.heappush(cards,c)

for _ in range(len(cards) - n):
    heapq.heappop(cards)

print((sum(cards)))
# 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 i in range(B):
    heapq.heappush(A, C)

print((sum(heapq.nlargest(N, 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 = sorted(BC, key= lambda x:x[1], reverse=True)


BC2 = []
for i in range(M):
  BC2.extend([BC[i][1]] * BC[i][0])
  if len(BC2) > N : break
A.extend(BC2)
A.sort(reverse=True)

print((sum(A[:N])))
# Original solution
def integerCards(n, m, alist, bclist):

    count = 0
    alist.sort()
    bclist.sort(key=lambda x: x[1], reverse=True)

    for b, c in bclist:
        for _ in range(b):
            if alist[count] < c:
                alist[count] = c
                count += 1
            if count == n:
                break
        if count == n:
            break

    return sum(alist)

def main():
    n, m = list(map(int, input().split()))
    alist = list(map(int, input().split()))
    bclist = [list(map(int, input().split()))for i in range(m)]
    print((integerCards(n, m, alist, bclist)))

if __name__ == '__main__':
    main()

# Optimized solution
def integerCards(n, m, alist, bclist):

    count = 0
    alist.sort()
    bclist.sort(key=lambda x: x[1], reverse=True)

    for b, c in bclist:
        for _ in range(b):
            if alist[count] < c:
                alist[count] = c
                count += 1
            else:
                break
            if count == n:
                break
        if count == n:
            break

    return sum(alist)

def main():
    n, m = list(map(int, input().split()))
    alist = list(map(int, input().split()))
    bclist = [list(map(int, input().split()))for i in range(m)]
    print((integerCards(n, m, alist, bclist)))

if __name__ == '__main__':
    main()