CodeEff/ECCO huggingface dataset:
# Original solution
# -*- coding: utf-8 -*-
# abc127/abc127_d
import sys
from operator import itemgetter

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

      


def main():
    N, M = i2nn()
    A = [(1, x) for x in i2nn()]
    S = [0] * M
    for j in range(M):
        S[j] = tuple(i2nn())
    S.extend(A)
    R = sorted(S, key=itemgetter(1))
    sum = 0
    while True:
        p = R.pop()
        if N - p[0] > 0:
            sum += p[0] * p[1]
            N -= p[0]
        else:
            sum += p[1] * N
            break
    print(sum)
    return

main()


# Optimized solution
# -*- coding: utf-8 -*-
# abc127/abc127_d
import sys
from operator import itemgetter

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))


def main():
    N, M = i2nn()
    A = [(1, x) for x in i2nn()]
    BC = [0] * M
    for j in range(M):
        BC[j] = tuple(i2nn())
    BC.extend(A)
    ABC = sorted(BC, key=itemgetter(1))
    sum = 0
    poped = ABC.pop()
    while N - poped[0] > 0:
        sum += poped[0] * poped[1]
        N -= poped[0]
        poped = ABC.pop()
    sum += poped[1] * N
    print(sum)
    return

main()
# Original solution

if __name__ == '__main__':
    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 += [c] * b
            
    a.sort(reverse=True)

    s = 0
    for i in range(n):
        s += a[i]
    
    print(s)


# Optimized solution

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

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

    bcn = 0
    for i in range(n):
        if(a[i] < bc[bcn][1]):
            a[i] = bc[bcn][1]
            bc[bcn][0] -= 1
            if(bc[bcn][0] == 0):
                bcn += 1
                if(bcn == m):
                    break

    print((sum(a)))
# Original solution
n,m= list(map(int,input().split()))
AA = list(map(int,input().split()))
A = [[AA[i],1] for i in range(n)]
for _ in range(m):
  b,c = list(map(int,input().split()))
  A += [[c,b]]
A.sort()
A.reverse()
rest = n
score = 0
while True:
  C = A[0][0]
  B = A[0][1]
  score += B * C
  rest -= B
  del A[0]
  if rest < 0:
    score += rest * C
    break
print(score)

# Optimized solution
n,m= list(map(int,input().split()))
AA = list(map(int,input().split()))
A = [(AA[i],1) for i in range(n)]
for _ in range(m):
  b,c = list(map(int,input().split()))
  A += [(c,b)]
A.sort()
A.reverse()
rest = n
score = 0
for (cc,bb) in A:
  use = min(bb,rest)
  rest -= use
  score += use*cc
print(score)
# Original solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
p = [[aa,1] for aa in a]
for _ in range(m):
  b = list(map(int,input().split()))
  b.reverse()
  p.append(b)
p.sort()
p.reverse()
rest = n
score = 0
for pp in p:
  use = min(pp[1],rest)
  rest -= use
  score += pp[0] * use
  if rest==0: break
print(score)

# Optimized solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
p = [[aa,1] for aa in a]
for _ in range(m):
  b = list(map(int,input().split()))
  b.reverse()
  p.append(b)
p.sort()
p.reverse()
rest = n
score = 0
for ni in range(n):
  use = min(p[ni][1],rest)
  rest -= use
  score += p[ni][0] * use
  if rest==0: break
print(score)
# Original solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
p = [[aa,1] for aa in a]
for _ in range(m):
  b = list(map(int,input().split()))
  b.reverse()
  p.append(b)
p.sort()
p.reverse()
rest = n
score = 0
for ni in range(n):
  use = min(p[0][1],rest)
  rest -= use
  score += p[0][0] * use
  del p[0]
  if rest==0: break
print(score)

# Optimized solution
#20:58
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
b = []
for i in range(m):
  now = list(map(int,input().split()))
  now.reverse()
  b.append(now)
b.sort()
b.reverse()
c = []
for i in range(m):
  c += [b[i][0]] * b[i][1]
  if len(c) > n:
    c = c[:n]
    break
if len(c) < n:
  c += [0] * (n-len(c))
ans = 0
for i in range(n):
  ans += max(a[i],c[i])
#print(a)
#print(c)
print(ans)
# Original solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
d = []
for _ in range(m):
  b,c = list(map(int,input().split()))
  d.append([c,b])
d.sort(reverse = True)
e = []
f = 0
for j in range(m):
  for k in range(d[j][1]):
    e.append(d[j][0])
    f += 1
    if f == n:
      break
  else:
    continue
  break
else:
  e += [0] * (n-len(e))
ans = 0
#print(a)
#print(e)
for i in range(n):
  ans += max(a[i],e[i])
print(ans)

# Optimized solution
#15:40
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
bc = []
for _ in range(m):
  bc.append(list(map(int,input().split())))
bc.sort(key=lambda x: -x[1])
d = []
dl = 0
for x in bc:
  b,c = x
  d += [c] * b
  dl += b
  if dl >= n:
    break
if dl < n:
  d += [0] * (n-dl)
ans = []
for i in range(n):
  ans.append(max(a[i],d[i]))
#print(a)
#print(d)
#print(ans)
print((sum(ans)))
# Original solution
from collections import Counter

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

for i in range(m):
    b, c = list(map(int, input().split()))
    for value in sorted(list(a.keys())):
        if value >= c:
            break
        if a[value] > 0:
            if a[value] >= b:
                a[value] -= b
                a[c] += b
                b = 0
            else:
                b -= a[value]
                a[c] += a[value]
                a[value] = 0
        if a[value] == 0:
            del a[value]
        if b == 0:
            break
    
ans = 0
for i in list(a.keys()):
    ans += i * a[i]
print(ans)

# Optimized solution
n, m = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
cb = []
for i in range(m):
    b, c = list(map(int, input().split()))
    cb.append([c, b])
cb.sort(reverse=True)

now = 0
for i in range(n):
    if a[i] < cb[now][0] and cb[now][1] > 0:
        a[i] = cb[now][0]
        cb[now][1] -= 1
    if cb[now][1] == 0:
        now += 1
    if now >= len(cb):
        break
print((sum(a)))
# Original solution
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))

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

bc.sort(key=lambda x:x[1],reverse=True)
newcard=[]
for b,c in bc:
    newcard.extend([c]*b)
    if(len(newcard)>=n):
        break

size = min(n,len(newcard))
a.sort()
for i in range(size):
    if(newcard[i]>a[i]):
        a[i]=newcard[i]
    else:
        break
print((sum(a)))

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

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

bc.sort(key=lambda x:x[1],reverse=True)
newcard=[]
for b,c in bc:
    newcard.extend([c]*b)
    if(len(newcard)>=n):
        break
a += newcard
a.sort(reverse=True)
print((sum(a[:n])))
# Original solution
import sys
input = sys.stdin.readline
from operator import itemgetter    

def solve():
    from operator import itemgetter

    turns = tuple(map(int, input().split()))[1]
    cardsList = list(map(int, input().split()))
    turnsList = [tuple(map(int, input().split())) for _ in range(turns)]
    
    for chances, num in sorted(turnsList, key=itemgetter(1), reverse=True):
        for i in range(chances):
            minCard = min(cardsList)
            if num > minCard:
                cardsList[cardsList.index(minCard)] = num
            elif i == 0:
                return print(sum(cardsList))
            else:
                break
    print(sum(cardsList))
solve()


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

def solve():
    cardsNum, turnsNum = tuple(map(int, input().split()))
    cards = sorted([int(x) for x in input().split()])
    turns = sorted([tuple(int(x) for x in input().split()) for _ in range(turnsNum)], key=itemgetter(1), reverse=True)
    
    largeCount = 0
    largeCards = [0,] * cardsNum
    for chances, num in turns:
        for _ in range(chances):
            if (largeCount < cardsNum):
                largeCards[largeCount] = num
                largeCount += 1
            else:
                break
        if (largeCount >= cardsNum):
            break 
    
    for i in range(cardsNum):
        if (largeCards[i] > cards[i]):
            cards[i] = largeCards[i]
        else:
            break
    print((sum(cards)))
solve()
# Original solution
import heapq
def sol():
    n,m=list(map(int,input().split()))
    a=[int(i) for i in input().split()]
    d={}
    w=[]
    q=[]
    for i in a:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
            w.append(i)
    for i in w: heapq.heappush(q, i)
    for i in range(m):
        b,c=list(map(int,input().split()))
        while b:
            if c>q[0]:
                x=min(b,d[q[0]])
                if c in d:
                    d[c]+=x
                    b-=x
                    d[q[0]]-=x
                    if d[q[0]]==0:
                        heapq.heappop(q)
                else:
                    d[c]=x
                    b-=x
                    d[q[0]]-=x
                    heapq.heappush(q,c)
                    if d[q[0]]==0:
                        heapq.heappop(q)
            else:
                break
    ans=chk=0
    for i in d:
        ans+=i*d[i]
    print(ans)

if __name__=="__main__":
    sol()

# Optimized solution
import heapq
n,m=list(map(int,input().split()))
a=[int(i) for i in input().split()]
d={}
w=[]
q=[]
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
        w.append(i)
for i in w: heapq.heappush(q, i)
for i in range(m):
    b,c=list(map(int,input().split()))
    while b:
        if c>q[0]:
            x=min(b,d[q[0]])
            if c in d:
                d[c]+=x
                b-=x
                d[q[0]]-=x
                if d[q[0]]==0:
                    heapq.heappop(q)
            else:
                d[c]=x
                b-=x
                d[q[0]]-=x
                heapq.heappush(q,c)
                if d[q[0]]==0:
                    heapq.heappop(q)
        else:
            break
ans=chk=0
for i in d:
    ans+=i*d[i]
print(ans)
# Original solution
import bisect

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

A.sort()

for i in range(M):
    B,C = list(map(int,input().split()))
    index = bisect.bisect_left(A,C)
    if index > B:
        A[:B] = [C] * B
    else:
        A[0:index] = [C] * index
    A.sort()

print((sum(A)))

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

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

cot = 0
add = 0

for b,c in B:
    cot += b
    if cot > N:
        add = N - cot + b
        A.extend([c] * add)
        break
    else:
        A.extend([c] * b)

print((sum(sorted(A, reverse = True)[:N])))
# Original solution
import heapq
import sys

input = sys.stdin.readline

def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    heapq.heapify(A)
    for i in range(M):
        B, C = list(map(int, input().split()))
        for j in range(B):
            s = min(A)
            if s < C:
                heapq.heappushpop(A, C)
            else:
                break
    ans = sum(A)
    print(ans)

if __name__ == "__main__":
    main()


# Optimized solution
import sys

input = sys.stdin.readline

def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    BC = []
    for _ in range(M):
        BC.append(tuple(map(int, input().split())))
    BC.sort(key=lambda x: x[1])
    vs = []; jtmp = 0
    for i in range(M):
        tmp = BC.pop()
        jtmp += tmp[0]
        if jtmp > N:
            vs.extend([tmp[1]]*(N-(jtmp-tmp[0])))
            break
        else:
            vs.extend([tmp[1]]*tmp[0])
    
    A.sort(reverse=True)
    vs.sort()
    ans = 0
    for _ in range(N):
        tmpA = A.pop()
        if len(vs) > 0:
            tmpC = vs.pop()
        else:
            tmpC = 0
        ans += tmpA*(tmpA>=tmpC) + tmpC*(tmpA<tmpC)
    print(ans)

if __name__ == "__main__":
    main()
# Original solution
def main():
    from collections import Counter
    n, m, *abc = list(map(int, open(0).read().split()))
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = list(a.keys())
    keys.sort(reverse=True)

    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    from collections import Counter
    n, m, *abc = list(map(int, open(0).read().split()))
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = sorted(list(a.keys()), reverse=True)
    
    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
import sys
from heapq import heappush, heappop
input = sys.stdin.readline

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

heap = []
for v in A:
    heappush(heap, (v * -1, 1))

for c, p in LR:
    heappush(heap, (p * -1, c))
    
res = 0
while N > 0:
    v, c = heappop(heap)
    v *= -1
    
    if N < c:
        res += v * N
        N = 0
    else:
        res += v * c
        N -= c
        
print(res)

# Optimized solution
import sys
from heapq import heappush, heappop
input = sys.stdin.readline

N, M = list(map(int, input().split()))
L = [int(v) for v in input().split()]
LL = [[int(v) for v in input().split()] for _ in range(M)]

heap = []
for a in L:
    heappush(heap, (-a, 1))

for a in LL:
    heappush(heap, (-a[1], a[0]))
    
l = N
ans = 0
for i in range(N + M):
    t = heappop(heap)
    
    if l >= t[1]:
        l -= t[1]
        ans += t[0] * t[1] * -1
    else:
        ans += l * t[0] * -1
        l = 0
        
    if l == 0:
        break
        
print(ans)
# Original solution
import sys
f=lambda:list(map(int,sys.stdin.readline().split()))
n,m=f()
l=sorted(f())
s=[]
t=0
for i in range(m):
  b,c=f()
  s+=[c]*b
  t+=b
s.sort(reverse=1)
a=0
for i in range(n):
  if i<t: a+=max(l[i],s[i])
  else: a+=l[i]
print(a)

# Optimized solution
import sys
f=lambda:list(map(int,sys.stdin.readline().split()))
n,m=f()
la=sorted(f())
ll=sorted([list(f()) for _ in range(m)],key=lambda k:-k[1])
ls=[]
t=0
for b,c in ll:
  if t+b>n:
    ls+=[c]*(n-t)
    t=n
    break
  ls+=[c]*b
  t+=b
ls.sort(reverse=1)
a=0
for i in range(n):
  if i<t: a+=max(la[i],ls[i])
  else: a+=la[i]
print(a)
# Original solution
import sys
f=lambda:list(map(int,sys.stdin.readline().split()))
n,m=f()
la=sorted(f())
ll=sorted([list(f()) for _ in range(m)],key=lambda k:-k[1])
ls=[]
t=a=0
for b,c in ll:
  if t+b>n: ls+=[c]*(n-t); t=n; break
  ls+=[c]*b; t+=b
for i in range(n):
  if i<t: a+=max(la[i],ls[i])
  else: a+=la[i]
print(a)

# Optimized solution
import sys
f=lambda:list(map(int,sys.stdin.readline().split()))
n,m=f();l=f();t=n
for b,c in sorted([f() for _ in range(m)],key=lambda k:-k[1]):
  l+=[c]*b;t+=b 
  if t>n*2:break
l.sort()
print((sum(l[-n:])))
# 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
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 _ in range(b):
        tmp = heapq.heappop(a)
        if tmp >= c:
            heapq.heappush(a, tmp)
            break
        else:
            heapq.heappush(a, c)
print((sum(a)))
# 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 _ in range(b):
        tmp = heapq.heappop(a)
        if tmp >= c:
            heapq.heappush(a, tmp)
            break
        else:
            heapq.heappush(a, c)
print((sum(a)))


# Optimized solution
n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
d = {}
for a in A:
    d[a] = 1 if a not in d else d[a] + 1
for _ in range(m):
    b, c = list(map(int, input().split()))
    d[c] = b if c not in d else d[c] + b
ans = 0
cnt = 0
L = sorted(d, reverse=True)
for k in L:
    if d[k] + cnt < n:
        ans += k * d[k]
        cnt += d[k]
    else:
        ans += k * (n - cnt)
        break
print(ans)
# Original solution
import bisect

n, m = list(map(int, input().split()))
a_array = sorted([int(x) for x in input().split()])
bc_array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x: x[1], reverse=True)

candidate_replace_cnt = n
replace_sum = 0
replace_cnt = 0
for b, c in bc_array:
    if a_array[0] > c and candidate_replace_cnt <= 0:
        break
    # 何枚入れられそうか
    num = bisect.bisect_left(a_array, c)
    # 入れ替えられる最大枚数が決まる
    candidate_replace_cnt = min(candidate_replace_cnt, num)
    # 全部入れ替えられる
    if candidate_replace_cnt <= b:
        replace_sum += c*candidate_replace_cnt
        a_array = a_array[candidate_replace_cnt:]
        break
    candidate_replace_cnt -= b
    replace_sum += c*b
    a_array = a_array[b:]
print((replace_sum + sum(a_array)))


# Optimized solution
import bisect

n, m = list(map(int, input().split()))
a_array = sorted([int(x) for x in input().split()])
bc_array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x: x[1], reverse=True)

# 何枚入れ替えられるか
candidate_replace_cnt = n
for b, c in bc_array:
    if a_array[0] >= c or candidate_replace_cnt < 0:
        break
    for i in range(b):
        a_array.append(c)
    candidate_replace_cnt -= b
a_array.sort(reverse=True)
print((sum(a_array[:n])))
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
P = [(A[i], 1) for i in range(N)]
for j in range(M):
    B, C = list(map(int, input().split()))
    P.append((C, B))
P.sort(reverse=True)
ans, cnt = 0, N
for v, c in P:
    use = min(c, cnt)
    ans += use*v
    cnt -= use
print(ans)

# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
CB = [list(map(int, input().split()))[::-1] for _ in range(M)]
CB.sort()
C, B = list(map(list, list(zip(*CB))))
b = B.pop()
c = C.pop()
ans = []
for a in A:
    if a < c:
        ans.append(c)
        b -= 1
    else:
        ans.append(a)
    if b == 0:
        if B:
            b = B.pop()
            c = C.pop()
        else:
            c = -1

print((sum(ans)))
# Original solution
N, M = list(map(int, input().split()))
from  bisect import bisect_right
inf = float("inf")
A = sorted(list(map(int, input().split())))
BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: -x[1])
cnt = 0
L, R = 0, N
I = []
for b, c in BC:
    idx = bisect_right(A[L:R], c)

    if idx == 0:
        I.append((L, R, 0, c))
        break
    elif idx < b:
        I.append((L+idx, R, idx, c))
        break
    elif idx >= b:
        I.append((L+idx, R, b, c))
        tmp = L
        L += b
        R = tmp + idx

    cnt += 1
    if cnt == M:
        I.append((L, R, 0, c))

S = [0]
for a in A:
    S.append(a+S[-1])

ans = 0
for L, R, x, c in I:
    ans += S[R] - S[L] + x*c

print(ans)




# Optimized solution
N, M = list(map(int, input().split()))
from  bisect import bisect_right
inf = float("inf")
A = sorted(list(map(int, input().split())))
BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: -x[1])
cnt = 0
L, R = 0, N
I = []
for b, c in BC:
    idx = bisect_right(A, c, lo=L, hi=R)
    idx -= L
    if idx == 0:
        I.append((L, R, 0, c))
        break
    elif idx < b:
        I.append((L+idx, R, idx, c))
        break
    elif idx >= b:
        I.append((L+idx, R, b, c))
        tmp = L
        L += b
        R = tmp + idx     

    cnt += 1
    if cnt == M:
        I.append((L, R, 0, c))

S = [0]
for a in A:
    S.append(a+S[-1])
ans = 0
for L, R, x, c in I:
    ans += S[R] - S[L] + x*c

print(ans)
# Original solution
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
sum=0
for i in range(n):
    sum+=a[i]
for i in range(m):
    b=list(map(int,input().split()))
    for i in range(b[0]):
        if a[i]<=b[1]:
            sum=sum-a[i]+b[1]
            a[i]=b[1]
    a.sort()
print(sum)

# Optimized solution
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
b=[]
sum=0
for i in range(m):
    b.append(list(map(int,input().split())))
b.sort(key=lambda x: x[1])
B=len(b)
b1=b[B-1][0]
b2=b[B-1][1]
b3=0
for i in range(n):
    if a[i]<b2 and b3==0:
        sum+=b2
        b1-=1
    else:
        sum+=a[i]
    if b1==0:
        B-=1
        if B==0:
            b3=1
        b1=b[B-1][0]
        b2=b[B-1][1]
print(sum)
# Original solution
import heapq
n,m = list(map(int, input().split()))

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

min_num = a[0]

tmp_array = []

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

sort_array = sorted(tmp_array, key=lambda x: x[1])

for i in range(m):
  b = sort_array[i][0]
  c = sort_array[i][1]
  if min_num >= c:
    continue
  else:
    for j in range(b):
      if a[0] < c:
        heapq.heappop(a)
        heapq.heappush(a, c)
      else:
        break
    min_num = a[0]

#for i in range(m):
#  b,c = map(int, input().split())
#  if min_num >= c:
#    continue
#  else:
#    for j in range(b):
#      if a[0] < c:
#        heapq.heappop(a)
#        heapq.heappush(a, c)
#      else:
#        break
#    min_num = a[0]

print((sum(a)))

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

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

min_num = a[0]

tmp_array = []

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

sort_array = sorted(tmp_array, key=lambda x: -x[1])

for i in range(m):
  b = sort_array[i][0]
  c = sort_array[i][1]
  if min_num >= c:
    continue
  else:
    for j in range(b):
      if a[0] < c:
        heapq.heappop(a)
        heapq.heappush(a, c)
      else:
        break
    min_num = a[0]

#for i in range(m):
#  b,c = map(int, input().split())
#  if min_num >= c:
#    continue
#  else:
#    for j in range(b):
#      if a[0] < c:
#        heapq.heappop(a)
#        heapq.heappush(a, c)
#      else:
#        break
#    min_num = a[0]

print((sum(a)))