CodeEff/ECCO huggingface dataset:
# Original solution
import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: list(map(int, input().split()))
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i:
        x, y = a[0]
        if x >= c:
            break
        d = min(i, y)
        i -= d
        y -= d
        if y:
            heapq.heapreplace(a, (x, y))
        else:
            heapq.heappop(a)
    heapq.heappush(a, (c, b - i))
print((sum(starmap(mul, a))))


# Optimized solution
import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: list(map(int, input().split()))
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i:
        x, y = a[0]
        if x >= c:
            break
        if y > i:
            heapq.heapreplace(a, (x, y - i))
            i = 0
        else:
            heapq.heappop(a)
            i -= y
    heapq.heappush(a, (c, b - i))
print((sum(starmap(mul, a))))
# Original solution
import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: list(map(int, input().split()))
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i and a[0][0] < c:
        x, y = a[0]
        if y > i:
            heapq.heapreplace(a, (x, y - i))
            i = 0
        else:
            heapq.heappop(a)
            i -= y
    heapq.heappush(a, (c, b - i))
print((sum(starmap(mul, a))))


# Optimized solution
import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: list(map(int, input().split()))
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i and a[0][0] < c:
        x, y = a[0]
        if y > i:
            heapq.heapreplace(a, (x, y - i))
            i = 0
        else:
            heapq.heappop(a)
            i -= y
    if i < b:
        heapq.heappush(a, (c, b - i))
print((sum(starmap(mul, a))))
# Original solution
n, m = list(map(int, input().split()))
a = [int(x) for x in input().split()]
for _ in range(m):
    b, c = list(map(int, input().split()))
    k = [c]*b
    a = a + k
a.sort()
a = a[-n::]
ans = sum(a)
print(ans)

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

for i in range(m):
    b, c = list(map(int, input().split()))
    p.append((c, b))
    
p.sort()
p.reverse()
ans, count = 0, n
for (s, t) in p:
    k = min(count, t)
    ans += s * k
    count -= t
    if count <= 0:
        break
    
print(ans)
# Original solution
import bisect

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

for _ in range(M):
    B, C = list(map(int, input().split()))
    i = bisect.bisect_right(A, C)
    if N <= i:
        A = A[B:i] + [C] * B + A[i:]
    elif i <= B:
        A[:i] = [C] * i
    else:
        A = A[B:i] + [C] * B + A[i:]
print((sum(A)))

# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
BC = []
for _ in range(M):
    B, C = list(map(int, input().split()))
    BC.append((B, C))
BC.sort(key=lambda bc: (bc[1], bc[0]), reverse=True)

ai = 0
bci = bcj = 0
while ai < N and bci < M:
    if A[ai] < BC[bci][1]:
        A[ai] = BC[bci][1]
        ai += 1
        bcj += 1
        if BC[bci][0] <= bcj:
            bci += 1
            bcj = 0
    else:
        ai += 1
print((sum(A)))
# Original solution
n,m=list(map(int,input().split()))
A=list(map(int,input().split()))
B=[];C=[];Q=[]
A.sort()
for i in range(m):
    b,c=list(map(int,input().split()))
    Q.append([b,c])

import bisect as bi

#Qの統合
s=set([l[1] for l in Q])
dicts={}
for i in s:
    dicts[i]=0
for l in Q:
    dicts[l[1]]+=l[0]
Q=[[j,i] for i,j in list(dicts.items())]
Q=sorted(Q, key=lambda x:x[1], reverse=1)
######
#print(Q)

for l in Q:
    b,c=l
    a=bi.bisect_left(A,c)
    if A[0]>=c:
        break
    if a< b:
        A=[c]*a + A[a:]
        break
    
    A= A[b:a]+ [c]*b + A[a:]
    #print(A)
print((sum(A)))

# Optimized solution
n,m=list(map(int,input().split()))
A=list(map(int,input().split()))
A.sort()
Q=[]
for i in range(m):
    b,c=list(map(int,input().split()))
    Q.append([b,c])

Q=sorted(Q, key=lambda x:x[1], reverse=1)
kae=0

d=[-1]*(n)
now=0
for l in Q:
    b,c=l
    if n-now<b:
        d[now:]=[c]*(n-now)
        break
    d[now:now+b]=[c]*b
    now+=b

#print(d)
ans=sum(A)
now=ans
for kae in range(1,n+1):
    now+=d[kae-1]
    now-=A[kae-1]
    ans=max(ans,now)
print(ans)
# Original solution
from heapq import *


n, m = list(map(int, input().split()))
PAIRS = [[-a, -1] for a in map(int, input().split())]
heapify(PAIRS)

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

answer = 0
for _ in range(n):
    pair = heappop(PAIRS)
    answer += -pair[0]
    pair[1] += 1
    if pair[1] != 0:
        heappush(PAIRS, pair)

print(answer)


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

for _ in range(m):
    b, c = list(map(int, input().split()))
    PAIRS.append((c, b))
PAIRS.sort(reverse = True)

answer, count = 0, 0
for pair in PAIRS:
    answer += pair[0] * pair[1]
    count += pair[1]
    if count > n:
        answer -= pair[0] * (count - n)
        break

print(answer)
# Original solution
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
d=[]
for i in range(m):
  b,c = list(map(int,input().split())) 
  d.extend([c]*b)
if n < len(d):
  d=d[:n]
d.sort()
d=d[::-1]
for i in range(len(d)):
  for j in range(n):
    if a[j] < d[i]:
      a[j]=d[i]
      break
print((sum(a)))

# Optimized solution
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
d=[]
for i in range(m):
  b,c = list(map(int,input().split())) 
  d.extend([c]*b)
if n < len(d):
  d=d[:n]
d.sort(reverse=True)
for i in range(len(d)):
  for j in range(n):
    if a[j] < d[i]:
      a[j]=d[i]
      break
print((sum(a)))
# Original solution
import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        for i, a_i in enumerate(a[start:start+count+1]):
            if a_i < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[start+i] = ope
            else:
                break
        start += i

    print(sum(a))

if __name__ == '__main__':

    ops = []
    n, m = list(map(int, sys.stdin.readline().strip().split(" ")))
    a = list(map(int, sys.stdin.readline().strip().split(" ")))
    for _ in range(m):
        b, c = list(map(int, sys.stdin.readline().strip().split(" ")))
        ops.append((c, b))

    solve(n, m, a, ops)

# Optimized solution
import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in range(start, start+count):
            if a_i >= n:
                break
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print(sum(a))

if __name__ == '__main__':

    ops = []
    n, m = list(map(int, sys.stdin.readline().strip().split(" ")))
    a = list(map(int, sys.stdin.readline().strip().split(" ")))
    for _ in range(m):
        b, c = list(map(int, sys.stdin.readline().strip().split(" ")))
        ops.append((c, b))

    solve(n, m, a, ops)
# Original solution
import heapq

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

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

heapq.heapify(a)

l = [[] for _ in range(m)]

for i in range(m):
    b,c = list(map(int,input().split()))
    l[i] = [c,b]
l.sort()
for i in range(m):
    b,c = l[i][1],l[i][0]
    for j in range(b):
        x = heapq.heappop(a)
        if(x < c):
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,x)
            break
print((sum(a)))

# Optimized solution
import heapq

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

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

heapq.heapify(a)

l = [[] for _ in range(m)]

for i in range(m):
    b,c = list(map(int,input().split()))
    l[i] = [c,b]
l.sort(reverse=True)
for i in range(m):
    b,c = l[i][1],l[i][0]
    for j in range(b):
        x = heapq.heappop(a)
        if(x < c):
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,x)
            break
print((sum(a)))
# Original solution
import heapq
n,m = list(map(int,input().split()))
a = [int(i) for i in input().split()]
b = [[int(i) for i in input().split()] for _ in range(m)]

heapq.heapify(a)
for i in range(m) :
    B = b[i][0]
    C = b[i][1]
    for j in range(B) :
        if a[0] < C :
            heapq.heappop(a)
            heapq.heappush(a,C)
        else :
            break
 
print((sum(a)))

# Optimized solution
n,m = list(map(int,input().split()))
a = [int(i) for i in input().split()]
b = [[int(i) for i in input().split()] for _ in range(m)]
a.sort()
b = sorted(b,key = lambda  x: x[1],reverse=True)
d = []
j = 0
while (n<=len(a) or j<m) :
    C = b[j][1]
    B = b[j][0]
    for i in range(B) :
        d.append(C)
    j += 1
    if j>=m or len(d) > len(a) :
        break

for i in range(min(len(d),len(a))) :
    if a[i] < d[i] :
        a[i] = d[i]

print((sum(a)))
# Original solution
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    for s in S:
        b = s[0]
        c = s[1]
        if c >= cards[-1]:
            cards = cards[b:] + [c for _ in range(b)]
            #print(cards)
            continue
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


# Optimized solution
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)
# Original solution
from heapq import heapify, heappop, heappush
from sys import stdin

N, M = list(map(int, input().split()))
A = list(map(int, stdin.readline().split()))
heapify(A)
BC = [None] * M
for i in range(M):
    BC[i] = tuple(map(int, stdin.readline().split()))
BC = sorted(BC, key=lambda x: x[1])

for bc in BC:
    for i in range(bc[0]):
        if bc[1] <= A[0]:
            break
        heappop(A)
        heappush(A, bc[1])

print((sum(A)))


# Optimized solution
from heapq import heapify, heappop, heappush
from sys import stdin

N, M = list(map(int, input().split()))
A = list(map(int, stdin.readline().split()))
heapify(A)
BC = [None] * M
for i in range(M):
    BC[i] = tuple(map(int, stdin.readline().split()))
BC = sorted(BC, key=lambda x: x[1], reverse=True)

enough = False
for bc in BC:
    if enough:
        break
    for i in range(bc[0]):
        if bc[1] <= A[0]:
            enough = True
            break
        heappop(A)
        heappush(A, bc[1])

print((sum(A)))
# Original solution
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for  _ in range(M)]#リストの表記が違う
BC.sort(key=lambda x: x[1],reverse=True)#リバースと-1の違い

for b,c in BC:
    A.extend([c]*b)
    if len(A)>N**2:
        break
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  _ in range(M)]#リストの表記が違う
BC.sort(key=lambda x: -x[1])#リバースと-1の違い

for b,c in BC:
    A.extend([c]*b)
    if len(A)>N**2:
        break
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])

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
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  _ in range(M)]#リストの表記が違う
BC.sort(key=lambda x: -x[1])#リバースと-1の違い

for b,c in BC:
    A.extend([c]*b)
    if len(A)>N*2:
        break
A.sort(reverse=True)
print((sum(A[:N])))
# Original solution
import heapq

n, m = list(map(int, input().split()))
a = sorted([int(i) for i in input().split()])
heapq.heapify(a)
l = []

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

for b, c in l:
    for _ in range(b):
        if a[0] < c:
            heapq.heappushpop(a, c)
        else:
            break

print((sum(a)))

# Optimized solution
import heapq

n, m = list(map(int, input().split()))
a = sorted([int(i) for i in input().split()])
heapq.heapify(a)
l = []

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

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

for b, c in l:
    if a[0] >= c:
        break
    for _ in range(b):
        if a[0] < c:
            heapq.heappushpop(a, c)
        else:
            break

print((sum(a)))
# Original solution
N, M = list(map(int,input().split()))
a = list(map(int,input().split()))
check = []
for i in range(M):
    check.append(list(map(int,input().split())))
check.sort(key=lambda x : x[1],reverse = True)
a.sort()
ans = []
for b, c in check:
    ans += [c for i in range(b)]
if len(ans) <= N:
    ans+=[0 for i in range(N-len(ans))]
A=0
for i in range(N):
    A+=max(ans[i],a[i])
print(A)

# Optimized solution
N, M = list(map(int,input().split()))
a = list(map(int,input().split()))
check = []
for i in range(M):
    check.append(list(map(int,input().split())))
check.sort(key=lambda x : x[1],reverse = True)
a.sort()
ans = []
for b, c in check:
    ans += [c for i in range(b)]
    if len(ans) > N:
        break
else:
    ans+=[0 for i in range(N-len(ans))]
A=0
for i in range(N):
    A+=max(ans[i],a[i])
print(A)
# Original solution
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
for i in range(M):
    B,C=list(map(int,input().split()))
    for j in range(B):
        A.append(C)
A.sort(reverse=True)
sum=0
for i in range(N):
    sum+=A[i]
print(sum)

# Optimized solution
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
A.sort(reverse=True)
D=[]
for i in range(M):
    (B,C)=list(map(int,input().split()))
    D.append((C,B))
D.append((0,0))
D.sort(reverse=True)
i=0
j=0
count=0
sum=0
while count<N:
    if A[i]>=D[j][0]:
        sum+=A[i]
        i+=1
        count+=1
    else:
        sum+=D[j][0]*(min(N-count,D[j][1]))
        count+=D[j][1]
        j+=1
print(sum)
# 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):
    a=heapq.heappop(A)
    if c>a:
      heapq.heappush(A,c)
    else:
      heapq.heappush(A,a)
      break
print((sum(A)))


# Optimized solution
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
L=[(1,a) for a in A]
for _ in range(M):
  b,c=list(map(int,input().split()))
  L.append((b,c))
L=sorted(L,key=lambda x: x[1],reverse=True)
ans,k=0,0
for n,a in L:
  if n+k>=N:
    ans+=a*(N-k)
    break
  else:
    ans+=a*n
    k+=n
print(ans)
# Original solution
N,M=list(map(int,input().split()))
L=list([(1,int(x)) for x in input().split()])
for _ in range(M):
  L.append(tuple(map(int,input().split())))
L=sorted(L,key=lambda x: x[1],reverse=True)
ans,k=0,0
for n,a in L:
  if n+k>=N:
    ans+=a*(N-k)
    break
  else:
    ans+=a*n
    k+=n
print(ans)

# Optimized solution
N,M=list(map(int,input().split()))
L=sorted(list([(1,int(x)) for x in input().split()])
         +[tuple(map(int,input().split())) for _ in range(M)]
         ,key=lambda x: x[1],reverse=True)
ans,k=0,0
for n,a in L:
  if n+k>=N:
    ans+=a*(N-k)
    break
  else:
    ans+=a*n
    k+=n
print(ans)
# Original solution
N,M=list(map(int,input().split()))
L=sorted(list([(1,int(x)) for x in input().split()])
         +[tuple(map(int,input().split())) for _ in range(M)]
         ,key=lambda x: x[1],reverse=True)
ans,k=0,0
for n,a in L:
  if n+k>=N:
    ans+=a*(N-k)
    break
  else:
    ans+=a*n
    k+=n
print(ans)

# Optimized solution
import sys
N,M=list(map(int,sys.stdin.readline().split()))
L=sorted(list([(1,int(x)) for x in sys.stdin.readline().split()])
         +[tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
         ,key=lambda x: x[1],reverse=True)
ans,k=0,0
for n,a in L:
  if n+k>=N:
    ans+=a*(N-k)
    break
  else:
    ans+=a*n
    k+=n
print(ans)
# Original solution
import bisect

card_count, rewrite_count = list(map(int, input().split(" ")))
cards = list(map(int, input().split(" ")))

cards.sort()

for _ in range(rewrite_count):
    stock_count, rewrite_number = list(map(int, input().split(" ")))
    insert_point = bisect.bisect_left(cards, rewrite_number)

    cards = cards[:insert_point] + ([rewrite_number] * stock_count) + cards[insert_point:]
    # for _ in range(stock_count):
    #     cards.insert(insert_point, rewrite_number)
    
    del cards[:stock_count]

print((sum(cards)))


# Optimized solution
import bisect

card_count, rewrite_count = list(map(int, input().split(" ")))

cards = {}
for card in list(map(int, input().split(" "))):
    count = cards.get(card, 0)
    cards[card] = count + 1

for _ in range(rewrite_count):
    stock_count, rewrite_number = list(map(int, input().split(" ")))
    count = cards.get(rewrite_number, 0)
    cards[rewrite_number] = count + stock_count

number_list = list(cards.keys())
number_list.sort(reverse=True)

total = 0
for number in number_list:
    if cards[number] < card_count:
        total += number * cards[number]
    else:
        total += number * card_count
        break
    card_count -= cards[number]

print(total)
# Original solution
N, M = list(map(int, input().split()))
a = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(M)]

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

for b, c in X:
  cnt = 0
  for i in range(N):
    if a[i] < c and cnt < b:
      a[i] = c
      cnt += 1
print((sum(a)))

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

X = [list(map(int, input().split())) for _ in range(M)]
X.sort(key=lambda x: x[1], reverse=True)
num_cnt = [x[0] for x in X]
val_cnt = [x[1] for x in X]

idx = 0
cnt = 0
ans = 0
cum = 0
for i in range(min(N, sum(num_cnt))):
  if val_cnt[idx] <= a[i]:
    print((sum(a[i:]) + ans))
    break
  ans += val_cnt[idx]
  cnt += 1
  cum += 1
  if num_cnt[idx] == cnt:
    idx += 1
    cnt = 0
  if cum == N:
    print(ans)
    break
else:
  print((sum(a[sum(num_cnt):] + [val_cnt[i] * num_cnt[i] for i in range(M)])))
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
d = []
for _ in range(M):
    b, c = list(map(int, input().split()))
    d += [c] * b

ans = []
i_a = 0
i_d = 0
MAX_D = len(d)

A.sort(reverse=True)
d.sort(reverse=True)

while len(ans) < N:
    if i_d < MAX_D and A[i_a] < d[i_d]:
            ans.append(d[i_d])
            i_d += 1
    else:
            ans.append(A[i_a])
            i_a += 1

print((sum(ans)))
    

# 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()
idx = 0

for b, c in sorted(X, key=lambda x: -x[1]):
    for j in range(idx, min(N, idx + b)):
        if A[j] < c:
            A[j] = c
    idx += b
print((sum(A)))
# Original solution
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,M = list(map(int,input().split()))
A = [int(i) for i in input().split()]
change = [0 for i in range(M)]
for i in range(M):
    change[i] = [int(i) for i in input().split()]

D = []
for i in range(M):
    b,c = change[i]
    for j in range(b):
        D += [c]

D.sort()
D.reverse()

A.sort()
ans = sum(A)
for i in range(min(len(D),len(A))):
    dif = D[i]-A[i]
    if dif < 0:
        break
    else:
        ans += dif
print(ans)


# Optimized solution
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,M = list(map(int,input().split()))
A = [int(i) for i in input().split()]
change = [0 for i in range(M)]
for i in range(M):
    change[i] = [int(i) for i in input().split()]

D = []
change = sorted(change,key=lambda x:x[1],reverse=True)
for i in range(M):
    b,c = change[i]
    for j in range(b):
        D += [c]
    if len(D) > N:
        break

A += D
A.sort(reverse=True)
print((sum(A[:N])))
# Original solution
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,M = list(map(int,input().split()))
A = [int(i) for i in input().split()]
change = [0 for i in range(M)]
for i in range(M):
    change[i] = [int(i) for i in input().split()]

D = []
change = sorted(change,key=lambda x:x[1],reverse=True)
for i in range(M):
    b,c = change[i]
    for j in range(b):
        D += [c]
    if len(D) > N:
        break

A += D
A.sort(reverse=True)
print((sum(A[:N])))


# Optimized solution
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,M = list(map(int,input().split()))
A = [int(i) for i in input().split()]
change = [0 for i in range(M)]
for i in range(M):
    change[i] = [int(i) for i in input().split()]

D = []
change = sorted(change,key=lambda x:x[1],reverse=True)
for i in range(M):
    b,c = change[i]
    # for j in range(b):
    #     D += [c]
    D += [c]*b
    if len(D) > N:
        break

A += D
A.sort(reverse=True)
print((sum(A[:N])))
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
D = []
for i in range(M):
  B,C = list(map(int, input().split()))
  D.extend([C]*B)

import bisect
from collections import deque

D = sorted(D,reverse=True)
A = sorted(A)
A.extend(D[:N])
A = sorted(A,reverse=True)

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


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

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

for i in BC:
  A.extend([i[1]]*i[0])
  if len(A) > 2*N:
    break
    
A = sorted(A,reverse=True)
print((sum(A[:N])))