CodeEff/ECCO huggingface dataset:
# Original solution
from operator import itemgetter


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

    asorted = sorted(alist)

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

    # print(f'initial: {asorted}')
    # print(f'bc: {bc}')

    fixed = []
    for b, c in bc:
        pick = [a for a in asorted if a >= c]

        if len(pick) > 0:
            asorted = asorted[:-len(pick)]
            fixed += pick

        if len(asorted) < 1:
            break

        for _ in range(b):
            if len(asorted) < 1:
                break
            asorted.pop(0)
            fixed.insert(0, c)

        # print(f'--- step n / {len(bc)} ---')
        # print(f'asorted: {asorted}')
        # print(f'pick   : {pick}')
        # print(f'fixed  : {fixed}')

    fixed += asorted

    print((sum(fixed)))


main()

# Optimized solution
from operator import itemgetter


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

    xy = [(1, ai) for ai in alist] + bc
    rest = n
    total = 0
    for number, score in sorted(xy, key=itemgetter(1), reverse=True):
        if rest <= number:
            total += score * rest
            break
        else:
            total += score * number
            rest -= number

    print(total)


main()
# Original solution
import sys
from collections import Counter
from bisect import insort_left

input = sys.stdin.readline

def main():
    N, M = list(map(int, input().split()))
    A = Counter(list(map(int, input().split())))
    
    A = sorted([[a, c] for a, c in list(A.items())])
    
    for i in range(M):
        B, C = list(map(int, input().split()))
        
        c = idx = 0
        for j in range(len(A)):
            if A[j][0] > C: break
        
            x = min(B, A[j][1])
            c += x
            B -= x
            A[j][1] -= x
            
            if not A[j][1]: idx += 1
            if not B: break
        
        if c: 
            for k in range(idx): A.pop(0)
                
            insort_left(A, [C, c])
    
    print((sum([a[0] * a[1] for a in A])))
    
if __name__ == '__main__':
    main() 

# Optimized solution
from operator import itemgetter

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

q = sorted(A+BC, key=itemgetter(1), reverse=True)

ans = 0
i = 0

while N:
    n = min(q[i][0], N)
    ans += q[i][1] * n
    N -= n

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

pool = []

for Ai in A:
    pool.append(Ai)

for Bi, Ci in BC:
    for _ in range(Bi):
        pool.append(Ci)

pool.sort(key=lambda x: -x)

print((sum(pool[: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)]


table = {}
for Ai in A:
    table[str(Ai)] = 0
for Bi, Ci in BC:
    table[str(Ci)] = 0
    
for Ai in A:
    table[str(Ai)] += 1

for Bi, Ci in BC:
    table[str(Ci)] += Bi

table2 = [(int(key), value) for key, value in list(table.items())]
table2.sort(key=lambda x: -x[0])

ans = ans_cnt = 0
for key, value in table2:
    # print("#", key, value, ans_cnt, ans)
    if ans_cnt + value >= N:
        ans += key * (N - ans_cnt)
        break
    else:
        ans_cnt += value
        ans += key * value

print(ans)
# Original solution
from collections import defaultdict as dd

def main():
    a = dd(int)
    n, m = [int(i) for i in input().split()]
    for i in input().split():
        a[int(i)] += 1

    for _ in range(m):
        b, c = [int(i) for i in input().split()]
        for _ in range(b):
            a[c]+=1
    res = 0
    cnt = 0
    for k in sorted(list(a.keys()))[::-1]:
        v = a[k]
        if cnt + v <= n:
            num = v
        else:
            num = n - cnt
        res += num * k
        cnt += num
        if cnt >= n:
            break
    print(res) 

if __name__ == '__main__':
    main()



# Optimized solution
def main():
    n, m = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    
    bc = []
    for _ in range(m):
        b, c = list(map(int, input().split()))
        bc.append((b, c))

    total = 0
    for num, v in sorted(bc, key=lambda x: -x[1]):
        total += num
        a.extend([v]*num)
        if total >= n:
            break
    print((sum(sorted(a)[-n:])))

if __name__ == '__main__':
    main()
# Original solution
n,m,*t=list(map(int,open(0).read().split()))
a=sorted(t[:n])[::-1]
m=0
for c,b in sorted(zip(t[n+1::2],t[n::2]))[::-1]:
 while a and b and c>a[-1]:m+=c;b-=1;a.pop()
print((m+sum(a)))

# Optimized solution
n,m,*t=list(map(int,open(0).read().split()))
a=sorted(t[:n])[::-1]
m=0
for c,b in sorted(zip(t[n+1::2],t[n::2]))[::-1]:
 while a and c>a[-1]and b:m+=c;b-=1;a.pop()
print((m+sum(a)))
# Original solution
n,m,*t=list(map(int,open(0).read().split()))
s=sorted
a=s(t[:n])[::-1]
i=n
for c,b in s(list(zip(t[n+1::2],t[n::2])))[::-1]:
 while c>a[i-1]and i*b:a[i-1]=c;b-=1;i-=1
print((sum(a)))

# Optimized solution
n,m,*t=list(map(int,open(0).read().split()))
s=sorted
a=s(t[:n])[::-1]
i=n
for c,b in s(list(zip(t[n+1::2],t[n::2])))[::-1]:
 while(c>a[i-1])*i*b:a[i-1]=c;b-=1;i-=1
print((sum(a)))
# Original solution
n,m,*t=list(map(int,open(0).read().split()))
s=sorted
a=s(t[:n])[::-1]
i=n
for c,b in s(list(zip(t[n+1::2],t[n::2])))[::-1]:
 while(c>a[i-1])*i*b:i-=1;a[i]=c;b-=1
print((sum(a)))

# Optimized solution
n,m,*t=list(map(int,open(0).read().split()))
s=sorted
a=s(t[:n])[::-1]
for c,b in s(list(zip(t[n+1::2],t[n::2])))[::-1]:
 while(c>a[n-1])*n*b:n-=1;a[n]=c;b-=1
print((sum(a)))
# Original solution
import heapq
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [-1 * x for x in a]
heapq.heapify(a)
for _ in range(m):
    b, c = list(map(int, input().split()))
    for i in range(b):
        heapq.heappush(a, -1 * c)

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

print(ans)

# Optimized solution
import heapq
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
heapq.heapify(a)
lst = []
for _ in range(m):
    b, c = list(map(int, input().split()))
    lst.append((b, c))

lst = sorted(lst, key = lambda x: -x[1])
flag = False
for b, c in lst:
    for _ in range(b):
        min_num = heapq.heappop(a)
        if min_num < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, min_num)
            flag = True
            break
    if flag:
        break

print((sum(a)))
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)
l = [list(map(int, input().split())) for i in range(m)]
l.sort(key=lambda x: x[1], reverse=True)
d = []
while l and len(d) <= n:
    bc = l.pop(0)
    d.extend([bc[1]]*bc[0])
ret = 0
for i in range(n):
    if d and d[0] > a[0]:
        ret += d.pop(0)
    else:
        ret += a.pop(0)
print(ret)

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

res = 0
pos_1 = 0
pos_2 = 0
for _ in range(n):
    if pos_2 == m or a[pos_1] > l[pos_2][1]:
        res += a[pos_1]
        pos_1 += 1
    else:
        res += l[pos_2][1]
        l[pos_2][0] -= 1
        if l[pos_2][0] == 0:
            pos_2 += 1
 
print(res)

# d = []
# while l and len(d) <= n:
#     bc = l.pop(0)
#     d.extend([bc[1]]*bc[0])
# ret = 0
# for i in range(n):
#     if d and d[0] > a[0]:
#         ret += d.pop(0)
#     else:
#         ret += a.pop(0)
# print(ret)
# Original solution
n,m = list(map(int, input().split()))

a = list(map(int,input().split()))
bclist = [list(map(int,input().split())) for _ in range(m)]

all = a

for bc in bclist:
    for i in range(bc[0]):
        all.append(bc[1])

all.sort()

print((sum(all[(len(all)-n):])))

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

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

all = []


for i in range(m):
    all.extend([bclist[i][1]]*bclist[i][0])
    if len(all) >n:
        break

all.extend(a)
all.sort(reverse=True)

print((sum(all[:n])))
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = list(map(int,readline().split()))
A=[int(x) for x in readline().split()]
BC=[]
for i in range(M):
  BC +=[list(map(int,readline().split()))]
BC = sorted(BC, key=lambda x: x[1],reverse = True)
A=sorted(A)
for i in range(M):
  for j in range(BC[i][0]):
    A[j]=max(A[j],BC[i][1])
  A=sorted(A)
print((sum(A)))

# Optimized solution
N,M=list(map(int,input().split()))
A=[int(x) for x in input().split()]
CB=[]
for i in range(M):
  B,C = list(map(int,input().split()))
  CB +=[[C,B]]

for j in range(N):
  CB +=[[A[j],1]]

CB=sorted(CB,reverse = True)
count = 0
result =0

i=0
while count<N:
  count +=CB[i][1]
  result +=CB[i][0]*CB[i][1]
  i +=1

result -= (count-N)*(CB[i-1][0])
print(result)
# Original solution
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return list(map(int, sys.stdin.readline().split()))
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def main():
    N, M = mi()
    A = sorted(li())

    '''
    for j in range(M):
        b, c = mi()
        ind = min(bisect.bisect_left(A, c), b)
        A = sorted([c]*ind + A[ind:])
    
    print(sum(A))
    '''
    for j in range(M):
        b, c = mi()
        A += [c]*b
    print((sum(sorted(A, reverse=True)[:N])))

if __name__ == "__main__":
    main()

# Optimized solution
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return list(map(int, sys.stdin.readline().split()))
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def main():
    N, M = mi()
    A = sorted(li())

    '''
    for j in range(M):
        b, c = mi()
        ind = min(bisect.bisect_left(A, c), b)
        A = sorted([c]*ind + A[ind:])
    
    print(sum(A))
    '''
    for _ in range(M):
        b, c = mi()
        for _ in range(b):
            A.append(c)
        
    print((sum(sorted(A, reverse=True)[:N])))

if __name__ == "__main__":
    main()
# Original solution
N, M = list(map(int, input().split()))

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

A_dict = {}

#Aをhash
for i in A:
    if i in A_dict:
        A_dict[i] += 1
    else:
        A_dict[i] = 1


for i in range(M):
    b, c = list(map(int, input().split()))
    for j in range(b):
        #最小値がc以上なら何もしない
        if min(A_dict.keys()) >= c:
            break
        else:
            if A_dict[min(A_dict.keys())] == 1:
                del A_dict[min(A_dict.keys())]
                if c in A_dict:
                    A_dict[c] += 1
                else:
                    A_dict[c] = 1
            else:
                A_dict[min(A_dict.keys())] -= 1
                if c in A_dict:
                    A_dict[c] += 1
                else:
                    A_dict[c] = 1

ans = 0
for k, v in list(A_dict.items()):
    ans += k * v
print(ans)

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

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

A_dict = {}

#Aをhash
for i in A:
    if i in A_dict:
        A_dict[i] += 1
    else:
        A_dict[i] = 1


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

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


card = 0
ans = 0
for i in A_dict:
    if card == N:
        break
    elif card + i[1] > N:
        ans += (N - card) * i[0]
        break
    else:
        ans += i[0] * i[1]
        card += i[1]
print(ans)
# 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()))
    bc.append([b, c])
    
sorted_a = sorted(a)
sorted_bc = sorted(bc, key=lambda x: x[1])

que = []
for b, c in sorted_bc:
    que += [c]*b
    
c = que.pop()    
ans = 0
for x in sorted_a:
    if x < c:
        ans += c
        if que:
            c = que.pop()
        else:
            c = 0
    else:
        ans += x
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])
    
a = sorted(a)
bc = sorted(bc, key=lambda x: x[1])

que = []
for b, c in bc:
    que += [c]*b


c = que.pop()
ans = 0
i = 0
while True:
    if a[i] < c:
        ans += c
        if que:
            c = que.pop()
            i += 1
        else:
            i += 1
            break
    else:
        break
print((ans + sum(a[i:])))
# Original solution

#AのリストにCのリストを加えて大きい順に並べ替えてNまでの和を求める

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

#Aの入力
A_list = list(map(int,input().split()))

#Aの末尾にCのリストを追加する
for i in range(M):
    bi,ci = list(map(int,input().split()))
    for j in range(bi):
        A_list.append(ci)

#A_Listを大きい順に並べ替える
A_list=sorted(A_list,reverse=True)

#N番目までの総和を求める
print((sum(A_list[0:N])))


# Optimized solution

#AのリストにCのリストを加えて大きい順に並べ替えてNまでの和を求める
N,M = list(map(int,input().split()))

#Aの入力
A_list = list(map(int,input().split()))

C_list = []

#Cのリストに追加する
for i in range(M):
    bi,ci = list(map(int,input().split()))
    C_list.append([bi,ci])

#C_listをCの値でソート
C_list=sorted(C_list, reverse=True, key=lambda x:x[1])

count = 0
for bi,ci in C_list:
    count += bi
    if count > N:
        #countがNより大きくなったらNより大きくなった分だけ使う
        bi = N - count + bi
    A_list.extend([ci]*bi)

#A_Listを大きい順に並べ替える
A_list=sorted(A_list,reverse=True)

#N番目までの総和を求める
print((sum(A_list[0:N])))
# Original solution

#AのリストにCのリストを加えて大きい順に並べ替えてNまでの和を求める
N,M = list(map(int,input().split()))

#Aの入力
A_list = list(map(int,input().split()))

C_list = []

#Cのリストに追加する
for i in range(M):
    bi,ci = list(map(int,input().split()))
    C_list.append([bi,ci])

#C_listをCの値でソート
C_list=sorted(C_list, reverse=True, key=lambda x:x[1])

count = 0
for bi,ci in C_list:
    count += bi
    #if count > N:
        #countがNより大きくなったらNより大きくなった分だけ使う
        #bi = N - count + bi
    A_list.extend([ci]*bi)

#A_Listを大きい順に並べ替える
A_list=sorted(A_list,reverse=True)

#N番目までの総和を求める
print((sum(A_list[0:N])))


# Optimized solution

#AのリストにCのリストを加えて大きい順に並べ替えてNまでの和を求める
N,M = list(map(int,input().split()))

#Aの入力
A_list = list(map(int,input().split()))

C_list = []

#Cのリストに追加する
for i in range(M):
    bi,ci = list(map(int,input().split()))
    C_list.append([bi,ci])

#C_listをCの値でソート
C_list=sorted(C_list, reverse=True, key=lambda x:x[1])

count = 0
for bi,ci in C_list:
    count += bi
    if count > N:
        #countがNより大きくなったらNより小さい分だけ使う
        bi = N - count + bi
        A_list.extend([ci]*bi)
        break
    A_list.extend([ci]*bi)

#A_Listを大きい順に並べ替える
A_list=sorted(A_list,reverse=True)

#N番目までの総和を求める
print((sum(A_list[0:N])))
# Original solution
def slove():
    import sys, heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    bc = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    heapq.heapify(a)
    for b, c in bc:
        for i in range(b):
            p = heapq.heappop(a)
            if p < c:
                heapq.heappush(a, c)
            else:
                heapq.heappush(a, p)
                break
    print((sum(a)))


if __name__ == '__main__':
    slove()


# Optimized solution
def slove():
    import sys, heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    bc = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    heapq.heapify(a)
    bc = sorted(bc, key=lambda x: x[1], reverse=True)
    for b, c in bc:
        bo = True
        for i in range(b):
            p = heapq.heappop(a)
            if p < c:
                heapq.heappush(a, c)
            else:
                heapq.heappush(a, p)
                bo = False
                break
        if not bo:
            break
    print((sum(a)))


if __name__ == '__main__':
    slove()
# Original solution
import bisect
from operator import itemgetter
n, m = list(map(int, input().split()))
A = sorted(list(map(int, input().split())))
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1))
for i in range(m):
  b, c = BC[i]
  t = bisect.bisect_left(A, c)
  if t > b:
    A = A[b:t] + [c]*b + A[t:]
  else:
    A[:t] = [c]*t
print((sum(A)))

# Optimized solution
from operator import itemgetter
n, m = list(map(int, input().split()))
A = [(1, i) for i in map(int, input().split())]
BC = [ tuple(map(int, input().split())) for _ in range(m) ]
XY = sorted(A + BC, reverse=True, key=itemgetter(1))
c = n
now = 0
ans = 0
while c > 0 and now < n+m:
  x, y = XY[now]
  t = min(c, x)
  ans += y*t
  c -= t
  now += 1
print(ans)
# Original solution
N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))

for m in range(M):
  B,C = list(map(int,input().split()))
  if A[0]<C:
    A+=B*[C]

A = sorted(A)[::-1]
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 m in range(M)]
BC = sorted(BC,key=lambda x:x[1])[::-1]

for b,c in BC:
  A.extend(b*[c])
  if 2*N<len(A):
    break

A = sorted(A)[::-1]
print((sum(A[:N])))
# Original solution
n,m = list(map(int, input().split()))
List = list(map(int, input().split()))
List.sort()
cand = []
for _ in range(m):
  b,c = list(map(int,input().split()))
  for i in range(b):
    cand.append(c)
cand.sort()
cand = cand[::-1]
chan = []
for i in range(min(len(List),len(cand))):
  if cand[i] >=List[i]:
    chan.append(cand[i])
  else:
    break
leng = len(chan)
ans = chan +List[leng:]
print((sum(ans)))

# Optimized solution
n,m = list(map(int, input().split()))
List = list(map(int, input().split()))
List.sort()
cand = []
for _ in range(m):
  b,c = list(map(int,input().split()))
  cand.append((b,c))
bc = sorted(cand, key=lambda x: x[1], reverse=True)
i = 0
for b, c in bc:
    while b:
        if i < n and List[i] < c:
            List[i] = c
            b -= 1
        else:
            break
        i += 1
print((sum(List)))
# Original solution
import collections

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
ac = collections.Counter(a)
for i in range(m):
    b, c = list(map(int, input().split()))
    x = sorted(ac.items())
    j = 0
    while b:
        y = x[j]
        if y[0] < c:
            if y[1] < b:
                ac[c] += y[1]
                del ac[y[0]]
                b -= y[1]
            else:
                ac[c] += b
                ac[y[0]] -= b
                b = 0
        else:
            break
        j += 1
ans = 0
for k, v in list(ac.items()):
    ans += k * v
print(ans)

# Optimized solution
from operator import itemgetter
import bisect

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=itemgetter(1), reverse=True)
bi = [bisect.bisect_left(a, bc[i][1]) for i in range(m)]
ans = 0
did = 0
for i in range(m):
    if bi[i] - did <= 0:
        continue
    if bi[i] - did > bc[i][0]:
        ans += bc[i][0] * bc[i][1]
        did += bc[i][0]
    else:
        ans += (bi[i] - did) * bc[i][1]
        did += (bi[i] - did)
print((sum(a[did:]) + ans))
# Original solution
N,M = list(map(int,input().split(" ")))
A = list(map(int,input().split(" ")))
B = [0]*M
for j in range(M):
	B[j] = list(map(int,input().split(" ")))

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

r = 0
for i in tmp:
	for k in range(r,N,1):
		if i[1] > A[k] and i[0] > 0:
			A[k] = i[1]
			i[0] -= 1
			r = k

print((sum(A)))

# Optimized solution
N,M = list(map(int,input().split(" ")))
A = list(map(int,input().split(" ")))
B = [0]*M
for j in range(M):
	B[j] = list(map(int,input().split(" ")))

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

r = 0
for i in tmp:
	for k in range(r,N,1):
		if i[1] > A[k] and i[0] > 0:
			A[k] = i[1]
			i[0] -= 1
			r = k+1
		elif A[k] > i[1] or i[0] == 0:
			break

print((sum(A)))
# Original solution
N,M = list(map(int,input().split()))
X = {}
for i in map(int,input().split()):
    if i in list(X.keys()):
        X[i] += 1
    else:
        X[i] = 1
for _ in range(M):
    b,c = list(map(int,input().split()))
    if c in list(X.keys()):
        X[c] += b
    else:
        X[c] = b

K = sorted(list(X.keys()),reverse=True)
res = 0
for k in K:
    if N >= X[k]:
        res += k*X[k]
        N -= X[k]
    else:
        res += k*N
        break

print(res)

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

j = 0
for i in range(N):
    if X[j][1] < A[i]:
        break
    else:
        X[j][0] -= 1
        A[i] = X[j][1]
    if X[j][0] == 0:
        j += 1
    if j == M:
        break

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

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

cards = list(map(int, input().split()))
cards.sort()
ops = []
for i in range(M):
    B, C = list(map(int, input().split()))
    ops.append({"B": B, "C": C})
ops.sort(key=lambda o: o["C"], reverse=True)
#print(cards)
#print(ops)

left = 0
for op in ops:
    length = bisect.bisect_left(cards, op["C"], lo=left) - left
    #print(length)
    # fill left..idx
    for i in range(op["B"]):
        if i < length:
            cards[left + i] = op["C"]
    left += min(length, op["B"])
#print(cards)
ans = 0
for val in cards:
    ans += val
print(ans)


# Optimized solution
import bisect

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

cards = list(map(int, input().split()))
cards.sort()
ops = []
for i in range(M):
    B, C = list(map(int, input().split()))
    ops.append({"B": B, "C": C})
ops.sort(key=lambda o: o["C"], reverse=True)
#print(cards)
#print(ops)

left = 0
for op in ops:
    length = bisect.bisect_left(cards, op["C"], lo=left) - left
    #print(length)
    # fill left..idx
    for i in range(min(length, op["B"])):
        cards[left + i] = op["C"]
    left += min(length, op["B"])
#print(cards)
ans = 0
for val in cards:
    ans += val
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)]

A.sort()

for i,j in BC:

    for k in range(i):
        if A[k] < j:
            A[k] = j
        else:
            break

    A.sort()

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()
S_BC = sorted(BC,key=lambda x:x[1],reverse=True)

index = 0
flag = 0
for Bj,Cj in S_BC:
    for k in range(Bj):
        if len(A) >= index+1:
            if A[index] < Cj:
                A[index] = Cj
                index += 1
            else:
                flag = 1
                break
        else:
            flag = 1
            break
        
    if flag == 1:
        break

print((sum(A)))