CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    #import sys
    #input = sys.stdin.readline
    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)
    append_list = []
    for b,c in BC:
        if len(append_list)>=n:
            break
        append_list+=[c]*b
    A+=append_list
    A.sort(reverse=True)
    print((sum(A[:n])))

if __name__=='__main__':
    main()

# Optimized solution
def main():
    import sys
    input = sys.stdin.readline
    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)
    append_list = []
    for b,c in BC:
        if len(append_list)>=n:
            break
        append_list+=[c]*b
    A+=append_list
    A.sort(reverse=True)
    print((sum(A[:n])))

if __name__=='__main__':
    main()
# Original solution
# D - Integer Cards

from operator import itemgetter
from collections import deque

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

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

BC = sorted(BC, key=itemgetter(1), reverse=True)

D = deque()
for _ in range(M):
    bc = BC.pop()
    for _ in range(bc[0]):
        D.append(bc[1])

for i in range(N):
    if len(D) != 0 and A[i] <= D[-1]:
        A[i] = D.pop()

print((sum(A)))


# Optimized solution
# D - Integer Cards

from operator import itemgetter

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

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

BC = sorted(BC, key=itemgetter(1), reverse=True)

ans = 0
for i in range(N):
    if len(BC) != 0 and A[i] <= BC[0][1]:
        ans += BC[0][1]
        BC[0][0] -= 1
        if BC[0][0] == 0:
            BC.pop(0)
    else:
        ans += A[i]

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

a.sort()

for i in range(M):
    b = bc[i][0]
    c = bc[i][1]
    a.extend([c for i in range(b)])

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

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

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

cnt = 0
for i in range(M):
    b = bc[i][0]
    c = bc[i][1]
    a.extend([c for i in range(b)])
    cnt += b
    if cnt > N:
        break

a.sort(reverse=True)
print((sum(a[:N])))
# Original solution
N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
BC = []
for i in range(M):
    a = list(map(int,input().split()))
    BC.append(a)
BC = sorted(BC, key = lambda x:x[1],reverse = True)
maxc = max([i[1] for i in BC])
Asub = [i for i in A if i <= maxc+1]
for b,c in BC:
    count = b
    Asub = sorted(Asub)
    for i in range(len(Asub)):
        if Asub[i] < c and count != 0:
            Asub[i] = c
            count -= 1
        else:
            break

print((sum(Asub) + sum(A[len(Asub):])))

# Optimized solution
def main():
    N,M = list(map(int,input().split()))
    A = sorted(list(map(int,input().split())))
    BC = []
    for i in range(M):
        a = list(map(int,input().split()))
        BC.append(a)
    BC = sorted(BC, key = lambda x:x[1],reverse = True)
    sum = 0
    for b,c in BC:
        if sum + b <= N:
            sum += b
            for i in range(b):
                A.append(c)
        else:
            sub = N - sum
            for i in range(sub):
                A.append(c)
    A = sorted(A,reverse = True)
    suma = 0
    for i in range(N):
        suma += A[i]
    print(suma)    

main()
# Original solution
import sys

input = sys.stdin.readline
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])

extend = A.extend
[extend([BC[i][1]] * BC[i][0]) for i in range(m)]

A = sorted(A, reverse=True)
print((sum(A[:n])))

# Optimized solution
import sys
 
input = sys.stdin.readline
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])
 
extend = A.extend
[extend([BC[i][1]] * BC[i][0]) for i in range(m)]
 
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])

extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC]
A.sort(reverse=True)

print((sum(A[:n])))

# Optimized solution
import sys

input = sys.stdin.readline
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])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print((sum(A[:n])))
# Original solution
def main():
    import heapq
    n,m = list(map(int,input().split()))
    a = list(map(int,input().split()))
    h = []
    for i in range(n):
        heapq.heappush(h,a[i])
    for i in range(m):
        b,c = list(map(int,input().split()))
        while h[0]<c and b>0:
            b = b-1
            heapq.heappop(h)
            heapq.heappush(h,c)
    print((sum(h)))
        


if __name__ == "__main__":
    main()


# Optimized solution
def main():
    n,m = list(map(int,input().split()))
    a = list(map(int,input().split()))
    h = {}
    for i in range(m):
        b,c = list(map(int,input().split()))
        if c not in list(h.keys()):
            h[c] = b
        else:
            h[c]+=b
    for i in range(n):
        if a[i] not in list(h.keys()):
            h[a[i]]=1
        else:
            h[a[i]]+=1
    ans = 0
    for k in sorted(list(h.keys()),reverse=True):
        if n<h[k]:
            ans += n*k
            break
        ans += h[k]*k
        n = n-h[k]
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
info=[]
for i in range(m):
    b,c=list(map(int,input().split()))
    info.append([c,b])
a=sorted(a) #小さい順に
info=sorted(info,reverse=True)
b=[] #n枚まで、大きい順に変えられるやつを記録
total=0
def add(num,s):
    global b
    for i in range(s):
        b.append(num)
        
for i in range(m):
    total+=info[i][1]
    if n<=total:
        total-=info[i][1]
        add(info[i][0],n-total)
    add(info[i][0],info[i][1])
l=len(b)
ans=0
for i in range(n):
    if i<=l-1:
        ans+=max(a[i],b[i])
    else:
        ans+=a[i]
print(ans)

# Optimized solution
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
info=[]
for i in range(m):
    b,c=list(map(int,input().split()))
    info.append([c,b])
a=sorted(a) #小さい順に
info=sorted(info,reverse=True)
b=[] #n枚まで、大きい順に変えられるやつを記録
total=0
def add(num,s):
    global b
    for i in range(s):
        b.append(num)
        
for i in range(m):
    total+=info[i][1]
    if n<=total:
        total-=info[i][1]
        add(info[i][0],n-total)
        break
    add(info[i][0],info[i][1])
l=len(b)
ans=0
for i in range(n):
    if i<=l-1:
        ans+=max(a[i],b[i])
    else:
        ans+=a[i]
print(ans)
# Original solution
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()))
    for i in range(b):
        a_list.append(c)
        
a_list.sort()
print((sum(a_list[::-1][0:n])))

# Optimized solution
n,m = list(map(int,input().split()))
a_list = list(map(int,input().split()))
b_list = []
for i in range(m):
    b_list.append(list(map(int,input().split())))
    
    
b_list.sort(key=lambda x: x[1],reverse=True)
cnt = 0
for i in range(m):
    for j in range(b_list[i][0]):
        if cnt > n:
            break
        a_list.append(b_list[i][1])
        cnt += 1
    
a_list.sort()
print((sum(a_list[::-1][0:n])))
# Original solution
n, m = list(map(int, input().split()))

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

for i in range(m):
    a, b = list(map(int, input().split()))
    for _ in range(a):
        A.append(b)

A = sorted(A)

print((sum(A[-n:])))

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

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

D = list(zip(C, B))
D = sorted(D)
C, B = list(zip(*D))
C = reversed(C)
B = reversed(B)
total = 0

for i, j in zip(C, B):
    if total >= n:
        break
    else:
        total += j
        A.extend([i] * j)

A = sorted(A)
print((sum(A[-n:])))
# Original solution
import bisect
n, m = list(map(int, input().split()))
arr = sorted(list(map(int, input().split())))
ope = []
d = []
for i in range(m):
    ope.append(list(map(int,input().split())))
ope = sorted(ope,key = lambda x:-x[1])
for b,c in ope:
    if len(d) == n:
        break
    elif len(d) + b > n:
        for i in range(n-b):
            d.append(c)
    else:
        for i in range(b):
            d.append(c)
d.reverse()
arr = sorted(arr,reverse = True)
x = [0]*(n+1)
x[0] = sum(arr)
for i in range(1,n+1):
    t_arr = arr.pop()
    if d:
        t_d = d.pop()
    else:
        t_d = t_arr
    x[i] = x[i-1] + t_d - t_arr
    if x[i] < x[i-1]:
        break
print((max(x)))


# Optimized solution
import bisect
n, m = list(map(int, input().split()))
arr = sorted(list(map(int, input().split())))
ope = []
d = []
for i in range(m):
    ope.append(list(map(int,input().split())))
ope = sorted(ope,key = lambda x:-x[1])
i = 0
ok = True
for b,c in ope:
    for rep in range(b):
        if i >= n or arr[i] > c:
            ok = False
            break
        arr[i] = c
        i += 1
    if ok:
        continue
    else:
        break
print((sum(arr)))
# Original solution
import sys
import bisect
N, M = list(map(int, input().split()))
A = sorted(map(int, input().split()))
for _ in range(M):
    b, c = list(map(int, sys.stdin.readline().split()))
    x = bisect.bisect_left(A, c)
    y = min(x, b)
    A = [c] * y + A[y:]
    if x != y:
        A.sort()
print((sum(A)))

# Optimized solution
import sys
import bisect
N, M = list(map(int, input().split()))
A = sorted(map(int, input().split()))
CB = [None] * M
for i in range(M):
    b, c = list(map(int, sys.stdin.readline().split()))
    CB[i] = (c, b)
CB.sort(reverse=True)

i = 0
ans = 0
for c, b in CB:
    x = bisect.bisect_left(A, c, i)
    count = min(x - i, b)
    ans += c * count
    i += count
for j in range(i, N):
    ans += A[j]
print(ans)
# Original solution
import heapq
import sys
input = sys.stdin.readline

def readlines(n):
    for _ in range(n):
        b, c = list(map(int, input().split()))
        yield b, c

def main():
    _, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    total = sum(A)
    heapq.heapify(A)

    for b, c in sorted(readlines(M), key=lambda x: -x[1]):
        for _ in range(b):
            o = heapq.heappushpop(A, c)
            if o < c:
                total += c - o
            else:
                break
            
    print(total)

main()

# Optimized solution
import heapq
import sys
input = sys.stdin.readline
from operator import itemgetter

def readlines(n):
    for _ in range(n):
        b, c = list(map(int, input().split()))
        yield b, c

def main():
    _, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    total = sum(A)
    heapq.heapify(A)

    for b, c in sorted(readlines(M), key=itemgetter(1), reverse=True):
        for _ in range(b):
            o = heapq.heappushpop(A, c)
            if o < c:
                total += c - o
            else:
                break
            
    print(total)

main()
# Original solution
from collections import Counter
from heapq import heapify, heappop, heappush


class Data:
    def __init__(self, value, count):
        self.value = value
        self.count = count

    def __lt__(self, other):
        return self.value > other.value
    # 降順に取り出す


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

q = list()
heapify(q)
for v, c in list(Counter(a).items()):
    heappush(q, Data(v, c))

for _ in range(M):
    c, v = list(map(int, input().split()))
    heappush(q, Data(v, c))

ans = 0
cnt = 0
while cnt < N:
    d = heappop(q)
    # print(d.value, d.count)
    chg = min(N - cnt, d.count)
    ans += chg * d.value
    cnt += chg

print(ans)


# Optimized solution
from heapq import heapify, heappush, heappop

N, M = list(map(int, input().split()))
a = list(map(int, input().split()))
hq = list([(-x, 1) for x in a])

heapify(hq)

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

rest = N
ans = 0
while rest > 0 and hq:
    mv, b = heappop(hq)
    mv *= -1
    use = min(rest, b)
    ans += mv * use
    rest -= use
print(ans)
# Original solution
from heapq import heapify, heappush, heappop

N, M = list(map(int, input().split()))
a = list(map(int, input().split()))
hq = list([(-x, 1) for x in a])

heapify(hq)

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

rest = N
ans = 0
while rest > 0 and hq:
    mv, b = heappop(hq)
    mv *= -1
    use = min(rest, b)
    ans += mv * use
    rest -= use
print(ans)


# Optimized solution
from heapq import heappop, heappush

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

hq = []
for aa in a:
    heappush(hq, (-aa, 1))

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

rest = n
ans = 0
while rest > 0:
    num, cnt = heappop(hq)

    num *= (-1)
    use = min(rest, cnt)
    ans += use * num
    rest -= use

print(ans)
# Original solution
def main():
    from collections import Counter
    from operator import itemgetter

    import sys
    input = sys.stdin.readline

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

    ctr = Counter(a)
    for _ in range(M):
        b, c = list(map(int, input().split()))
        ctr[c] += b

    ans = 0
    rest = N
    for integer, count in sorted(list(ctr.items()), key=itemgetter(0), reverse=True):
        take = min(rest, count)
        ans += take * integer
        rest -= take
        if not rest:
            break

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()


# Optimized solution
def main():
    from collections import defaultdict
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

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

    ctr = defaultdict(int)
    for x in A:
        ctr[x] += 1

    for _ in range(M):
        num_of_cards, int_written_on_cards = list(map(int, input().split()))
        ctr[int_written_on_cards] += num_of_cards

    rest = N
    total = 0
    for int_written_on_cards, num_of_cards in sorted(list(ctr.items()), key=itemgetter(0), reverse=True):
        take = min(rest, num_of_cards)

        total += int_written_on_cards * take
        rest -= take

        if rest == 0:
            break

    print(total)


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

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

a.sort()

d = []
loop = 0

while True:
        for b, c in bc:
                d.extend([c] * b)
                loop += 1
        if len(d) > n:
                break
        elif loop == m:
                break

while True:
        if a[0] < d[0]:
                a.append(d[0])
                del a[0]
                del d[0]
        else:
                break
        
        if d == []:
                break

print((sum(a)))

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

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

a.sort()

for b, c in bc:
        if c > a[0]:
                for i in range(b):
                        if c > a[0]:
                                del a[0]
                                a.append(c)
                        else:
                                break
        else:
                break


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

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

a.sort()

for b, c in bc:
        if c > a[0]:
                for i in range(b):
                        if c > a[0]:
                                del a[0]
                                a.append(c)
                        else:
                                break
        else:
                break


print((sum(a)))

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

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

a.sort()

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

        else:
                break
        if a_count == n:
                break        

print((sum(a)))
# Original solution
from io import StringIO
from collections import *
from functools import *
import sys


def main(inputs):
    # n = int(next(inputs))
    # n, k = map(int, next(inputs).split())
    # xs = list(map(int, next(inputs).split()))
    n, m = list(map(int, next(inputs).split()))
    an = list(map(int, next(inputs).split()))[:n]
    an.sort()
    bc = [ list(map(int, next(inputs).split())) for _ in range(m) ]
    bc.sort(key=lambda bc: bc[1]) # sort by c
    ans = 0
    for b, c in bc:
        for i in range(b):
            if an[i] < c:
                an[i] = c
                pass
            pass
        an.sort()
        pass
    return sum(an)


def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    print((main(gen_inputs())))
    pass


# Optimized solution
from io import StringIO
from collections import *
from functools import *
import sys


def main(inputs):
    # n = int(next(inputs))
    # n, k = map(int, next(inputs).split())
    # xs = list(map(int, next(inputs).split()))
    n, m = list(map(int, next(inputs).split()))
    an = list(map(int, next(inputs).split()))[:n]
    an.sort()
    bc = [ list(map(int, next(inputs).split())) for _ in range(m) ]
    bc.sort(key=lambda bc: bc[1], reverse=True) # sort by c
    
    x = 0
    y = 0
    ans = 0
    for i in range(n):
        if x < m and bc[x][1] >= an[i]:
            ans += bc[x][1]
            y += 1
            if y >= bc[x][0]:
                x += 1
                y = 0
                pass
            pass
        else:
            ans += an[i]
            pass
        pass
    return ans

def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    print((main(gen_inputs())))
    pass
# Original solution
from heapq import heapify,heappop,heappush

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

heapify(A)

for j in range(M):
    B = []
    for i in range(BC[j][0]):
        b = heappop(A)
        if b < BC[j][1]:
            b = BC[j][1]
        B.append(b)
    for i in range(BC[j][0]):
        heappush(A,B[i])

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

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

pt,card,index = 0,BC[0][1],0
while True:
    for i in range(BC[index][0]):
        if pt < N:
            A[pt] = max(A[pt],card)
        else:
            break
        pt += 1

    index += 1
    if index < M:
        card = BC[index][1]
    else:
        break

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=sorted(a)
k=[[int(i) for i in input().split()] for i in range(m)]
k=sorted(k,key=lambda x:-x[1])

now=0
flag=True
for x,y in k:
    if flag:
        for i in range(x):
            if flag and i+now<n:
                if y>a[i+now]:
                    a[i+now]=y
                else:
                    flag=False
    now+=x
print((sum(a)))

# Optimized solution
def main():
    import sys
    input=sys.stdin.readline
    n,m=list(map(int,input().split()))
    a=list(map(int,input().split()))
    a=sorted(a)
    k=[[int(i) for i in input().split()] for i in range(m)]
    k=sorted(k,key=lambda x:-x[1])
    
    now=0
    flag=True
    for x,y in k:
        if flag:
            for i in range(x):
                if i+now>=n:
                    print((sum(a)))
                    exit()
                if flag:
                    if y>a[i+now]:
                        a[i+now]=y
                    else:
                        flag=False
        now+=x
    print((sum(a)))
if __name__=="__main__":
    main()
# Original solution
n,m = list(map(int,input().split()))
a = [i for i in map(int,input().split())]
bc = [[i for i in map(int,input().split())] for j in range(m)]

a.sort(reverse=True)
bc.sort(key=lambda x: x[1], reverse=True)
arr = []
j = 0
for i in range(n):
  arr.append(bc[j][1])
  bc[j][0]-=1
  if bc[j][0]==0:
    j += 1
  if j >= m:
    break

while len(arr) < n:
  arr.append(a.pop(0))
arr.sort()

for i in range(len(a)):
  if arr[0] < a[0]:
    arr[0] = a.pop(0)
  arr.sort()
  
print((sum(arr)))

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

a.sort()
bc.sort(key=lambda x: x[1], reverse=True)
j = 0
for i in range(n):
  if a[i] < bc[j][1]:
    a[i]=bc[j][1]
    bc[j][0]-=1
    if bc[j][0]==0:
      j += 1
    if j >= m:
      break
print((sum(a)))
# Original solution
N, M = list(map(int, input().split()))
A_list = list(map(int, input().split()))
A_list.sort()

BC_list = [list(map(int, input().split())) for _ in range(M)]
BC_list = [BC_list[i][1] for i in range(M) for _ in range(BC_list[i][0])]
A_list.extend(BC_list)
A_list.sort()

print((sum(A_list[-N:])))


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

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

ans = 0
count = 0
i = N-1
m = M-1
while count < N:
    if A_list[i] < BC_list[m][1]:
        for _ in range(BC_list[m][0]):
            ans += BC_list[m][1]
            count += 1
            if count >= N:
                break
        m -= 1
    else:
        ans += A_list[i]
        count += 1
        i -= 1

    if m < 0:
        break

for _ in range(count, N):
    ans += A_list[i]
    i -= 1

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 += [C]*B
A.sort(reverse=True)

print((sum(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 += [C]*B
    A.sort(reverse=True)
    A = A[:N]
print((sum(A)))