CodeEff/ECCO huggingface dataset:
# Original solution
#coding:utf-8
import sys
N,M=list(map(int,input().split()))
A=[-1]*(3*(10**5))
p=0
A=list(map(int,input().split()))
Q=[]
for i in range(M):
    b,c=list(map(int,sys.stdin.readline().split()))
    Q.append((c,b))
Q.sort();Q.reverse();    
A.sort()
A.reverse()        

for c,b in Q:
    if A[-1] < c:
        A+=[c]*b
        A.sort(); A.reverse()
        A=A[:N]
print((sum(A[:N])))

# Optimized solution
#coding:utf-8
import sys
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
p=0
Q=[]
for a in A: Q.append((a,1))
for i in range(M):
    b,c=list(map(int,sys.stdin.readline().split()))
    Q.append((c,b))
Q.sort();Q.reverse()
n=0;s=0
for c,b in Q:
    if b+n<=N:
        s+=c*b
        n+=b
    else:
        s+=c*(N-n)
        break
print(s)
# Original solution
import sys
import bisect


def main():

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

    a.sort()
    a = tuple(a)

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

    num = 0
    ans = 0

    for i in range(m):
        b = bc[i][0]
        c = bc[i][1]
        index = bisect.bisect_left(a[num:],c)
        if index == 0:
            break
        elif index > b:
            ans += c * b
        else:
            ans += c * index
            ans += sum(a[num+index:num+b])

        num += b
        if num >= n:
            break

    if num < n:
        print((ans + sum(a[num:])))
    else:
        print(ans)
if __name__ == '__main__':
    input = sys.stdin.readline
    main()


# Optimized solution
import sys

def main():
    input = sys.stdin.readline

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

    a.sort()
    a = tuple(a)

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

    num = 0
    ans = 0

    for i in range(m):
        b = bc[i][0]
        c = bc[i][1]
        for j in range(num,min(num+b,n)):
            if c > a[j]:
                ans += c
            else:
                ans += a[j]

        num += b
        if num >= n:
            break

    if num < n:
        print((ans + sum(a[num:])))
    else:
        print(ans)
if __name__ == '__main__':
    main()
# Original solution
#python3
from heapq import heappop, heappush

def main():
    n, m = list(map(int, input().split()))
    hq = [] 
    for i in input().split():
        heappush(hq, (-int(i), 1))
    for _ in range(m):
        b, c = list(map(int, input().split()))
        heappush(hq, (-c, b))
    ans = 0
    for i in range(n):
        v, u = heappop(hq)
        u = u - 1
        if u >= 1:
            heappush(hq, (v, u))
        v = - v 
        ans = ans + v
    print(ans)
main()


# Optimized solution
#python3
def main():
    n, m = list(map(int, input().split()))
    cards = [(int(i), 1) for i in input().split()]
    for _ in range(m):
        b, c = list(map(int, input().split()))
        cards.append((c, b))
    cards.sort(reverse=True)
    ans = 0
    sumv = 0
    for i in range(n):
        v = cards[i][1]
        cv = cards[i][0] * v
        ans += cv
        sumv += v
        if sumv >= n:
            ans -= cards[i][0] * (sumv - n)
            break
    print(ans)
main()
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heappush, heapify 
def main():
    N, M = list(map(int, readline().split()))
    A = [int(i) for i in readline().split()]
    heapify(A)
    for _ in range(M):
        b, c = list(map(int, readline().split()))
        for i in range(b):
            v = heappop(A)
            if v>=c:
                heappush(A, v)
                break
            else:
                heappush(A, c)
    print((sum(A)))     
if __name__ == '__main__':
    main()


# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heappush, heapify 
def main():
    N, M = list(map(int , readline().split()))
    hp = [(-int(i), 1) for i in readline().split()]
    heapify(hp)
    for _ in range(M):
        b, c = list(map(int, readline().split()))
        heappush(hp, (-c, b))
    ans = 0
    while 1:
        if N <= 0:
            break
        if not len(hp):
            break
        v, u = heappop(hp)
        v = -v
        if N >= u:
            ans += v*u
            N += -u
        else:
            ans += v*N 
            N += -u
    print(ans)
if __name__ == '__main__':
    main()
# Original solution
n, m = list(map(int, input().split()))
a = sorted([int(i) for i in input().split()], reverse=True)

cs = []

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

cs = sorted(cs, reverse=True)

ind_a, ind_c = 0, 0
ans = 0

for i in range(n):
    if len(cs)-1 >= ind_c:
        if a[ind_a] >= cs[ind_c]:
            ans += a[ind_a]
            ind_a += 1
        else:
            ans += cs[ind_c]
            ind_c += 1
    else:
        ans += a[ind_a]
        ind_a += 1

print(ans)

# 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((b, c))

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

cnt = 0

for b, c in bc:
    cnt += b
    a += [c] * b
    if cnt >= n:
        break

print((sum(sorted(a,reverse=True)[:n])))
# Original 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(key=lambda x:x[1],reverse=True)
for chenge in BC:
    kaisuu = chenge[0];  value = chenge[1]
    cnt = 0
    for i in range(len(A)):
        if A[i] < value:
            A[i] = value
            cnt += 1
        if cnt == kaisuu:
            break
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(key=lambda x:x[1],reverse=True)
i = 0
for bc in BC:
    for _ in range(bc[0]):
        if i > len(A)-1:
            break
        if A[i] > bc[1]:
            break
        A[i] = bc[1]
        i += 1
print((sum(A)))
# Original solution
n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]

for j in range(m):
    new_a = sorted(a)
    for b in range(bc[j][0]):
        if new_a[b] < bc[j][1]:
            new_a[b] = bc[j][1]
    a = new_a
print((sum(a)))

# Optimized solution
n, m = (int(i) for i in input().split())
a = [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]), 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
N,M=list(map(int, input().split()))
A=list(map(int, input().split()))
A=sorted(A)

L=[[0,0] for _ in range(M)]
for i in range(M):
    b,c=list(map(int, input().split()))
    L[i][0]=b
    L[i][1]=c

L=sorted(L,reverse=True, key=lambda x: x[1])
X=[]
for l in L:
    b=l[0]
    c=l[1]
    n=min(b,N-len(X))
    X=X+[c]*n
    if len(X)==N:
        break
#print(X)
ans=0
for i in range(N):
    if len(X)>i:
        ans+=max(X[i],A[i])
    else:
        ans+=A[i]

print(ans)

# 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 a in A:
    L.append((1,a))
L=sorted(L, reverse=True, key=lambda x: x[1])
ans=0
count=N
for l in L:
    n,v=l
    ans+=v*min(count, n)
    count-=n
    if count<=0:
        break

print(ans)
# Original solution
import heapq
N,M=list(map(int,input().split()))
A = list(map(int,input().split()))
heapq.heapify(A)
l = [] 
for i in range(M):
  tmp = list(map(int,input().split()))
  l.append([tmp[1],tmp[0]])
l.sort(reverse=True)


for i,j in l:
  for I in range(j):
    Q = heapq.heappop(A)
    if Q<i :
      heapq.heappush(A,i)
    else:
      heapq.heappush(A,Q)
      break
# print(A)
print((sum(A)))

# Optimized solution
N,M=list(map(int,input().split()))
A = list(map(int,input().split()))
l = [] 
for i in range(M):
  tmp = list(map(int,input().split()))
  l.append([tmp[1],tmp[0]])
l.sort(reverse=True)
for i,j in l:
    A.extend([i]*j)
    if len(A)>2*N:break
A.sort(reverse=True)
print((sum(A[:N])))
# Original solution
N, M = list(map(int, input().split()))
A = sorted(map(int, input().split()))
L = []
for _ in range(M):
    b, c = list(map(int, input().split()))
    for _ in range(b):
        L.append(c)
L.sort(reverse=True)

idx = 0
for i in range(N):
    if (idx > len(L) - 1):
        break
    if (A[i] < L[idx]):
        A[i] = L[idx]
        idx += 1
    else:
        break

print((sum(A)))


# Optimized solution
N, M = list(map(int, input().split()))
A = sorted(map(int, input().split()))
L = []
for _ in range(M):
    b, c = list(map(int, input().split()))
    L.append([b, c])
L.sort(key=lambda x: x[1], reverse=True)
# 変更前のカードの枚数
# 変更後のカードの枚数
# をそれぞれ保存しておく

idx = 0
for i in range(N):
    if (idx > len(L) - 1):
        break
    if (A[i] < L[idx][1]):
        A[i] = L[idx][1]
        L[idx][0] -= 1
        if (L[idx][0] != 0):
            continue
        else:
            idx += 1
    else:
        break
print((sum(A)))
# Original solution
from heapq import heapify, merge, nlargest
from operator import itemgetter

n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
bcbc = [list(map(int, input().split())) for _ in range(m)]
heapify(aa)
bcbc.sort(key=itemgetter(1), reverse=True)

for b, c in bcbc :
    cc = [c]*min(b, n)
    dd = merge(aa, cc)
    dd = nlargest(n, dd)
    if aa == dd :
        break
    aa = dd
print((sum(dd)))

# Optimized solution
from operator import itemgetter

n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
bcbc = [list(map(int, input().split())) for _ in range(m)]
bcbc.extend([[1, a] for a in aa])
bcbc.sort(key=itemgetter(1), reverse=True)

count = 0
s = 0
for b, c in bcbc :
    if count + b >= n :
        b = n - count
    count += b
    s += b*c
    if count == n :
        break
print(s)
# Original solution
import bisect
# N, M = 10, 3
# ARR = [1, 8, 5, 7, 100, 4, 52, 33, 13, 5]
# BRR = [
#     [3, 10],
#     [4, 30],
#     [1, 4]
# ]
N,M = list(map(int,input().split()))
ARR = list(map(int,input().split()))
BRR = []
for i in range(M):
    BRR.append(list(map(int,input().split())))

def calculate(n, m, arr, brr):
    brr = sorted(brr, key=lambda x: -x[1])
    arr = sorted(arr)
    result = 0
    sIndex = 0
    for mIndex in range(m):
        br = brr[mIndex]
        kIndex = min(bisect.bisect_left(arr[sIndex:len(arr)],br[1]),br[0])
        if kIndex == 0:
            break
        result = result + kIndex*br[1]
        sIndex = sIndex + kIndex

    result = result + sum(arr[sIndex:len(arr)])

    print(result)

calculate(N, M, ARR, BRR)

# Optimized solution
# N, M = 10, 3
# ARR = [1, 8, 5, 7, 100, 4, 52, 33, 13, 5]
# BRR = [
#     [3, 10],
#     [4, 30],
#     [1, 4]
# ]


N,M = list(map(int,input().split()))
ARR = list(map(int,input().split()))
BRR = []
for i in range(M):
    BRR.append(list(map(int,input().split())))

def calculate(n, m, arr, brr):
    raw = []
    for ar in arr:
        raw.append([ar, 1])
    for br in brr:
        raw.append([br[1], br[0]])

    raw = sorted(raw,key=lambda x:-x[0])
    # print(raw)

    offset = 0
    sum = 0
    for ra in raw:
        if offset + ra[1] <= n:
            sum = sum + ra[1] * ra[0]
            offset = offset + ra[1]
        else:
            sum = sum + (n - offset) * ra[0]
            offset = n
            break
    print(sum)

calculate(N, M, ARR, BRR)
# Original solution
N, M = list(map(int, input().split()))
As = list(map(int, input().split()))
As.sort()
for m in range(M):
  B, C = list(map(int, input().split()))
  count = 0
  for i in range(B):
    if As[i] < C:
      count += 1
    else:
      break
  As[0:count] = []
  #print(As)
  index = N-count
  for i in range(N-count):
    if As[i] > C:
      index = i
      break
  As[index:index] = [C]*count
  #print(As)
print((sum(As)))


# Optimized solution
N, M = list(map(int, input().split()))
As = list(map(int, input().split()))
As.sort()
BCs = []
for m in range(M):
  B, C = list(map(int, input().split()))
  BCs.append((B, C))
BCs.sort(key=lambda BC: -BC[1])
#print(BCs)

index = 0
for m in range(M):
  B, C = BCs[m]
  for i in range(B):
    if index >= N:
      break
    if As[index] < C:
      As[index] = C
      index += 1
    else:
      break
print((sum(As)))
# Original solution
n,m = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
C = []
for i in range(m):
  b,c = list(map(int,input().split()))
  for i in range(b):
    C.append(c)
    
Cs = sorted(C)
CS = Cs[::-1]
ans = 0

if len(CS)<n:
  CS = CS +[0]*(n-m+1)
for i in range(n):
  ans += max(A[i],CS[i])

print(ans)
  


# Optimized solution
n,m=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
l=sorted([list(map(int,input().split())) for i in range(m)],reverse=True,key=lambda x: x[1])
 
c_l=[]
for b,c in l:
  c_l+=[c]*b
  if len(c_l)>=n:
    break
 
for i in range(min(n,len(c_l))):
  a[i]=max(a[i],c_l[i])
 
print((sum(a)))
# Original solution
import heapq

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

heapq.heapify(A)
for b, c in BC:
    for i in range(b):
        a = heapq.heappop(A)
        if a < c:
            heapq.heappush(A, c)
        else:
            heapq.heappush(A, a)

print((sum(A)))

# Optimized solution
import heapq

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

heapq.heapify(A)

BC = sorted(BC, key = lambda x : x[1], reverse=True)
for b, c in BC:
    for i in range(b):
        a = heapq.heappop(A)
        if a < c:
            heapq.heappush(A, c)
        else:
            heapq.heappush(A, a)
            break

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 i in range(m)]
b, c = [list(i) for i in zip(*bc)]

sum_b = sum(b)

for i in range(m):
    add = [c[i] for _ in range(b[i])]
    a.extend(add)
a.sort()
a = a[sum_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 i in range(m)]
bc = sorted(bc, key = lambda x : x[1], reverse=True)

sum_b = 0
for b, c in bc:
    sum_b += b
    a += [c] * b
    if n < sum_b:
        break
a.sort(reverse=True)
a = a[:n]

print((sum(a)))
# Original solution
from sys import stdin
from collections import deque
N, M = list(map(int, stdin.readline().rstrip().split()))
A = [int(x) for x in stdin.readline().rstrip().split()]
A.sort()
A = deque(A)
Y = []
for _ in range(M):
    b, c = [int(x) for x in stdin.readline().rstrip().split()]
    Y.extend([c] * b)
Y.sort()
Y = deque(Y)

for i in range(len(Y) if len(Y) < len(A) else len(A)):
    a = A.popleft()
    c = Y.pop()
    if a < c:
        A.append(c)
    else:
        A.append(a)
        print((sum(A)))
        quit()
print((sum(A)))

# Optimized solution
from sys import stdin
from collections import deque
from operator import itemgetter

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
A.sort()
A = deque(A)
X = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
X.sort(key=itemgetter(1), reverse=True)
D = []
for b, c in X:
    if len(D) < N:
        D.extend([c] * b)
    else:
        break
D = deque(D)

for i in range(len(D) if len(D) < len(A) else len(A)):
    a = A.popleft()
    c = D.popleft()
    if a < c:
        A.append(c)
    else:
        A.append(a)
        print((sum(A)))
        quit()
print((sum(A)))
# Original solution
import sys

input = sys.stdin.readline

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

cards = sorted(A)
op.sort(key=lambda x: -x[1])

i = 0

for m in range(M):
    b, c = op[m]
    for _ in range(b):
        if cards[i] < c:
            cards[i] = c
            i += 1
        if i >= N:
            break
    else:
        continue
    break

print((sum(cards)))


# Optimized solution
import sys

input = sys.stdin.readline

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

cards = sorted(A)
op.sort(key=lambda x: -x[1])

i = 0

for m in range(M):
    b, c = op[m]
    for _ in range(b):
        if cards[i] < c:
            cards[i] = c
            i += 1
            if i >= N:
                break
        else:
            break
    else:
        continue
    break

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

n, m = list(map(int, input().split()))
a = [ -int(x) for x in input().split() ]
bc = []
heapq.heapify(a)

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

bc.sort(key=lambda x: -x[1])
min_a = min(a)

for b, c in bc:
    if c < min_a:
        min_a = c
        continue
    for _ in range(b):
        heapq.heappush(a, -c)

ans = 0
for i in range(n):
    t = (-heapq.heappop(a))
    ans += t
print(ans)



# Optimized solution
n, m = list(map(int, input().split()))
a = sorted([ int(x) for x in input().split() ], reverse=True)
bc = []

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

bc.sort(key=lambda x: -x[1])
i, j, cnt, ans = 0, 0, 0, 0

while cnt < n:
    if j < m and a[i] < bc[j][1]:
        b, c = bc[j]
        ans += c * min(n-cnt, b)
        j += 1
        cnt += b
    else:
        ans += a[i]
        i += 1
        cnt += 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 i in range(m)]
for b,c in bc:
    a.extend([c]*b)
a.sort(reverse=True)
print((sum(a[:n])))

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

total = 0
D = []
A = sorted(A, key=lambda x:x[1], reverse=True)
for b, c in A:
    if len(D) >= N:
        break
    D.extend([c]*b)
print((sum(D[:N])))
# Original solution
import heapq

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

heapq.heapify(A)

for b, c in BC:
    cnt = 0
    for _ in range(b):
        p = heapq.heappop(A)
        if p > c:
            heapq.heappush(A, p)
            break
        else:
            cnt += 1

    _ = [heapq.heappush(A, c) for _ in range(cnt)]

print((sum(A)))


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

# n番目の要素でソートsort
BC = sorted(BC, reverse=True, key=lambda x: x[1])

m = A[0]
D = []
for b, c in BC:
    if c > m:
        _ = [D.append(c) for i in range(b)]
    else:
        continue
    if len(D) > N:
        break

D.append(0)

for i, d in enumerate(D):
    if i >= N:
        break
    if A[i] < d:
        A[i] = d
    else:
        break

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 i in range(m)]

a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
d = []
for i in bc:
    for j in range(i[0]):
        d.append(i[1])
#print(d)

if len(d) < n:
    for i in range(n-len(d)):
        d.append(0)

ans = 0
for i in range(n):
    if a[i] < d[i]:
        ans += d[i]
    else:
        ans += a[i]
print(ans)

# Optimized 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)]

for i in a:
    bc.append([1,i])
bc.sort(key=lambda x:x[1],reverse=True)
#print(bc)
ans = 0
for i in bc:
    d = min(i[0],n)
 #   print(d)
    ans += i[1] * d
    n -= d
print(ans)
# Original solution
import os, sys, re, math

N, M = [int(s) for s in input().split(' ')]

cards = [int(s) for s in input().split(' ')]
cards.sort()

bc_ary = []
for i in range(M):
    bc_ary.append([int(s) for s in input().split(' ')])

for bc in bc_ary:
    cnt = 0
    idx = 0
    while idx < N and cnt < bc[0]:
        mincard = min(cards)
        if mincard >= bc[1]:
            break
        if mincard < bc[1]:
            cards[cards.index(mincard)] = bc[1]
            cnt += 1
        idx += 1

print((sum(cards)))


# Optimized solution
import os, sys, re, math, heapq

N, M = [int(s) for s in input().split(' ')]

dic = {}
cards =  [int(s) for s in input().split(' ')]
for c in cards:
    if c in dic:
        dic[c] += 1
    else:
        dic[c] = 1

for i in range(M):
    b,c = [int(s) for s in input().split(' ')]
    if c in dic:
        dic[c] += b
    else:
        dic[c] = b

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

ret = 0
for k in keys:
    ret += min(N, dic[k]) * k
    N = N - dic[k]
    if N <= 0:
        break

print(ret)
# Original solution
from heapq import heappop, heappush

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

h = []

for x in a:
    heappush(h, x)

for b, c in bc:
    for _ in range(b):
        temp = heappop(h)
        if temp >= c:
            heappush(h, temp)
            break
        else:
            heappush(h, c)

print((sum(h)))



# Optimized solution
from heapq import heappop, heappush

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

bc.sort(reverse=True)

h = []

for x in a:
    heappush(h, x)

for b, c in bc:
    for _ in range(b):
        temp = heappop(h)
        if temp >= c:
            heappush(h, temp)
            break
        else:
            heappush(h, c)

print((sum(h)))
# Original solution
#TLE
N, M = list(map(int, input().split()))
a_list = list(map(int, input().split()))

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

a_list.sort(reverse = True)

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


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

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

written_nums.sort(reverse = True)
append_list = []
for c, b in written_nums:
    append_list += [c for _ in range(b)]

    if len(append_list) >= N:
        break

a_list += append_list
a_list.sort(reverse = True)

print((sum(a_list[:N])))
# Original solution
N,M=list(map(int,input().split()))
list1=list(map(int,input().split()))
list2=[]
for _ in range(M):
  B,C=list(map(int,input().split()))
  if C>min(list1):
    list2+=[C]*B  
list3=list1+list2
list3.sort(reverse=True)
list5=list3[:N]
SUM=sum(list5)
print(SUM)

# Optimized solution
N,M=list(map(int,input().split()))
list1=list(map(int,input().split()))
list2=[1]
for _ in range(M):
  B,C=list(map(int,input().split()))
  if C>min(list2) and len(list2)>N:
    list2+=[C]*B
  else:
    list2+=[C]*B
list3=list1+list2
list3.sort(reverse=True)
list5=list3[:N]
SUM=sum(list5)
print(SUM)
# Original solution
N,M=list(map(int,input().split()))
list1=list(map(int,input().split()))
list2=[]
for _ in range(M):
  B,C=list(map(int,input().split()))
  list2+=[C]*B
list2.sort(reverse=True)
list2=list2[:N]
list3=list1+list2
list3.sort(reverse=True)
list5=list3[:N]
SUM=sum(list5)
print(SUM)

# Optimized solution
N,M=list(map(int,input().split()))
list1=list(map(int,input().split()))
list2=[]
for _ in range(M):
  B,C=list(map(int,input().split()))
  list2+=[C]*B
  list2.sort(reverse=True)
  list2=list2[:N]
list3=list1+list2
list3.sort(reverse=True)
list5=list3[:N]
SUM=sum(list5)
print(SUM)