CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
for i in range(0,m):
    b, c = list(map(int, input().split()))
    for j in range(0,b):
        if a[j] < c:
            a[j] = c
        else:
            break
    if b != n:
        if a[b] < c:
            temp = []
            for j in range(0, n-b):
                if a[b] < c:
                    temp.append(a.pop(b))
                else:
                    break
            a = temp + a
print((sum(a)))

# Optimized solution
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
b_c_hash = {}
c_list = []
for i in range(0,m):
    b, c = list(map(int, input().split()))
    if c in b_c_hash:
        b_c_hash[c] += b
    else:
        b_c_hash[c] = b
        c_list.append(c)
c_list.sort(reverse=True)
k = 0
flag = 0
for c in c_list:
    for i in range(0, b_c_hash[c]):
        if k == n:
            flag = 1
            break
        if a[k] < c:
            a[k] = c
            k += 1
        else:
            flag = 1
            break
    if flag == 1:
        break
print((sum(a)))
# Original solution
N, M=list(map(int, input().split()))
a=list(map(int, input().split()))
a.sort()

import bisect

for i in range(M):
  b, c=list(map(int, input().split()))
  t=min(b, bisect.bisect(a,c)) # c以下の要素数
  a[:t]=[c]*t
  a.sort()
print((sum(a)))
  

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

A.sort()
# 書き換え得点がでかい順に並べる
BC.sort(key= lambda x : -x[1])

i = 0
f=0
for b, c in BC:
    for j in range(b):
      # 見てるとこがはみ出してないかつ、cより小さい
      if i+j<n and A[i+j]<c:
        A[i+j]=c
      else: # もう走査しても意味ないからぶれーく
        break
    i+=b
print((sum(A)))
# Original solution
import bisect

N, M = list(map(int, input().split()))
A = [int(_) for _ in input().split()]
B = [0] * M
C = [0] * M
A.sort()
#print(A)
for m in range(M):
    b, c = list(map(int, input().split()))
    index = bisect.bisect_right(A, c)
    #print(f'index >> {index}')
    if index > 0:
        if index - b < 0:
            A[:index] = [c] * index
        else:
            A[: index - b] = A[b: index]
            A[index - b: index] = [c] * b
    #print(A)

print((sum(A)))

# Optimized solution
import sys
N, M = list(map(int, input().split()))
A = [int(_) for _ in input().split()]
A.sort()
#print(A)
BC = [0] * M
for m in range(M):
    BC[m] = list(map(int, input().split()))
BC.sort(key=lambda x: x[1], reverse=True)
#print(BC)
c = 0
for m in range(M):
    for t in range(BC[m][0]):
        if BC[m][1] > A[c]:
            A[c] = BC[m][1]
        c += 1
        if c == N:
            print((sum(A)))
            sys.exit()
print((sum(A)))
# Original solution
N, M = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]
B = [0] * M
C = [0] * M
for j in range(M):
    B[j], C[j] = [int(a) for a in input().split()]

D = list(zip(C, B))
D = sorted(D, reverse=True) # Cで降順ソート
C, B = list(zip(*D))  # 統合していた配列を元に戻す

# C[0]>= C[1] >= ... >= C[M-1]となるように並び替え、
# B[0]枚をC[0]に、B[1]枚をC[1]に書き換えていく。
# すべてのカードがC[j]以上というjに到達したらおしまい。
A.sort()

k = 0 # 現在書き換えを検討しているカード
for j in range(M):
    for _ in range(B[j]):
        if k >= N or A[k] >= C[j]: break
        A[k] = C[j]
        k += 1

print((sum(A)))

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

D = list(zip(C, B))
D = sorted(D, reverse=True) # Cで降順ソート
C, B = list(zip(*D))  # 統合していた配列を元に戻す

# C[0]>= C[1] >= ... >= C[M-1]となるように並び替え、
# B[0]枚をC[0]に、B[1]枚をC[1]に書き換えていく。
# すべてのカードがC[j]以上というjに到達したらおしまい。
A.sort()

k = 0 # 現在書き換えを検討しているカード
for j in range(M):
    for _ in range(B[j]):
        if k >= N or A[k] >= C[j]: break
        A[k] = C[j]
        k += 1
    else:
        continue
    break

print((sum(A)))
# Original solution
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
from collections import defaultdict
d = defaultdict(int)
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = sorted(A)
for i in range(M):
    b,c = list(map(int,input().split()))
    d[c] += b
d = dict(d)
d = sorted(list(d.items()),key = lambda x:x[0],reverse = True)
n = len(d)
index = 0
for i in range(n):
    d[i] = list(d[i])
D = [0] * N
index = 0
for k in range(N):
    if d[index][1] != 0:
        d[index][1] -= 1
        D[k] = d[index][0]
    else:
        index += 1
        if index  == n:
            break
        else:
            d[index][1] -= 1
            D[k] = d[index][0]  
Max = 0
for X in range(N+1):
    s = 0
    for v in range(N):
        if v < X:
            s += D[v]
        else:
            s += A[v]
    Max = max(s,Max)
print(Max)


# Optimized solution
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
from collections import defaultdict
d = defaultdict(int)
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = sorted(A)
for i in range(M):
    b,c = list(map(int,input().split()))
    d[c] += b
d = dict(d)
d = sorted(list(d.items()),key = lambda x:x[0],reverse = True)
n = len(d)
index = 0
for i in range(n):
    d[i] = list(d[i])
D = [0] * N
index = 0
for k in range(N):
    if d[index][1] != 0:
        d[index][1] -= 1
        D[k] = d[index][0]
    else:
        index += 1
        if index  == n:
            break
        else:
            d[index][1] -= 1
            D[k] = d[index][0]  
Max = 0

for p in A:
    Max += p
for X in range(N):
    if A[X] < D[X]:
        Max += D[X] - A[X]
    else:
        break
print(Max)
# Original solution
import sys
import heapq
N,M=list(map(int,input().split()))
alist=list(map(int,input().split()))

cblist=[]
for i in range(M):
  B,C=list(map(int,input().split()))
  cblist.append((C,B))
cblist.sort(reverse=True)

hq=[]
for a in alist:
  heapq.heappush(hq,a)
  
for C,B in cblist:
  for i in range(B):
    if C<hq[0]:
      print((sum(hq)))
      sys.exit(0)
    else:
      heapq.heapreplace(hq,C)
else:
  print((sum(hq)))

# Optimized solution
import sys
import heapq
N,M=list(map(int,input().split()))
alist=list(map(int,input().split()))

cblist=[]
for i in range(M):
  B,C=list(map(int,input().split()))
  cblist.append((C,B))
cblist.sort(reverse=True)

hq=[]
for a in alist:
  heapq.heappush(hq,a)
  
for C,B in cblist:
  for i in range(B):
    if C<=hq[0]:
      print((sum(hq)))
      sys.exit(0)
    else:
      heapq.heapreplace(hq,C)
else:
  print((sum(hq)))
# Original solution
n,m = list(map(int,input().split()))
a_n = list(map(int,input().split()))
b_and_c = []
for i in range(m):
    b_and_c.append(list(map(int,input().split())))

for i in range(m):
    a_n.sort()
    for j in range(b_and_c[i][0]):
        if a_n[j] < b_and_c[i][1]:
            a_n[j] = b_and_c[i][1]
        else:
            break

print((sum(a_n)))

# Optimized solution
n,m = list(map(int,input().split()))
a_n = list(map(int,input().split()))
b_and_c = []
for i in range(m):
    b_and_c.append(list(map(int,input().split())))

a_n.sort()

b_and_c.sort(key = lambda x : x[1], reverse = True)
index = 0
for i in range(m):
    if index >= n:
        break
    elif a_n[index] >= b_and_c[i][1]:
        break
    for j in range(index, n):
        if a_n[j] < b_and_c[i][1]:
            for k in range(j, min(j + b_and_c[i][0], n)):
                if a_n[k] < b_and_c[i][1]:
                    a_n[k] = b_and_c[i][1]
                else:
                    break
            index = k + 1
            break

print((sum(a_n)))
# Original solution
#!/usr/bin/env python3
import sys
import heapq
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    heapq.heapify(A)

    for b, c in zip(B, C):
        for i in range(b):
            v = heapq.heappop(A)
            if v < c:
                heapq.heappush(A, c)
            else:
                heapq.heappush(A, v)
                break
    return sum(A)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    result = solve(N, M, A, B, C)
    print(result)

if __name__ == '__main__':
    main()

# Optimized solution
#!/usr/bin/env python3
import sys
import heapq
import bisect
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    ret = sum(A)
    cs = Counter(A)
    for c in C:
        if c not in cs:
            cs[c] = 0
    vs = sorted(cs.keys())

    i = 0
    while cs[vs[i]] == 0:
        i += 1

    for b, c in zip(B, C):
        while 0 < b:
            if c <= vs[i]:
                break
            bb = min(b, cs[vs[i]])
            b -= bb
            cs[vs[i]] -= bb
            cs[c] += bb
            ret += bb * (c - vs[i])
            if cs[vs[i]] == 0:
                i += 1
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    result = solve(N, M, A, B, C)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()
# 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):
        mn = heapq.heappop(a)
        if mn < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, mn)
            break

print((sum(a)))

# Optimized solution
import heapq

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
heapq.heapify(a)
bc = sorted(
    [list(map(int, input().split())) for _ in range(m)],
    reverse=True,
    key=lambda x: x[1],
)

for i in bc:
    b, c = i
    for _ in range(b):
        mn = heapq.heappop(a)
        if mn < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, mn)
            break

print((sum(a)))
# Original solution
d = input().split()
N = int(d[0])
M = int(d[1])
d = input().split()
As = [int(num) for num in d]
As.sort()


def main():
    lis = []
    for i in range(1, M+1):
        d = input().split()
        b = int(d[0])
        c = int(d[1])
        lis.append([c, b])
    lis = sorted(lis,key=lambda x:(-x[0], x[1]))
    count = 0
    asum = 0
    tmp = [0 for i in range(N)]
    for c, b in lis:
        for i in range(count, b+count):
            if i < N:
                tmp[i] = c
        count += b
    for i in range(N):
        if tmp[i] > As[i]:
            asum += tmp[i]
        else:
            asum += As[i]
    print(asum)
        

if __name__ == '__main__':
    main()





# Optimized solution
d = input().split()
N = int(d[0])
M = int(d[1])
d = input().split()
As = [int(num) for num in d]
As.sort()


def main():
    lis = []
    for i in range(1, M+1):
        d = input().split()
        b = int(d[0])
        c = int(d[1])
        lis.append([c, b])
    lis = sorted(lis,key=lambda x:(-x[0], x[1]))
    count = 0
    asum = 0
    tmp = [0 for i in range(N)]
    for c, b in lis:
        if count < N:
            for i in range(count, b+count):
                if i < N:
                    tmp[i] = c
            count += b
    for i in range(N):
        if tmp[i] > As[i]:
            asum += tmp[i]
        else:
            asum += As[i]
    print(asum)
        

if __name__ == '__main__':
    main()
# Original solution
import sys
import os
import bisect
from operator import itemgetter

N, M = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort()
B = [ 0  for _ in range(M)]
for i in range(M):
    b,c = list(map(int,input().split()))
    B[i] = [b,c]
B = sorted(B,key=itemgetter(1),reverse=True)
for i in range(M):
    id = bisect.bisect_left(A,B[i][1])
    if id > 0:
        for j in range(min(B[i][0],id+1)):
            if A[0] < B[i][1]:
                A.append(B[i][1])
                del A[0]
    else:
        break
print((sum(A)))


# Optimized solution
import sys
import os
import bisect
from operator import itemgetter

N, M = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort()
B = [ 0  for _ in range(M)]
for i in range(M):
    b,c = list(map(int,input().split()))
    B[i] = [b,c]
B = sorted(B,key=itemgetter(1),reverse=True)
ans = 0
for i in range(M):
    id = bisect.bisect_left(A,B[i][1])
    if id > 0:
        for j in range(min(B[i][0],id+1)):
            if len(A) > 0 and A[0] < B[i][1]:
                ans += B[i][1]
                del A[0]
    else:
        break
print((sum(A)+ans))
# Original solution
import sys
from heapq import heapify, heapreplace

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m = list(map(int, read().split()))
    a = [int(i) for i in read().split()]
    heapify(a)
    for _ in range(m):
        b, c = list(map(int, read().split()))
        for _ in range(b):
            if a[0] < c:
                heapreplace(a, c)
            else:
                break
    print((sum(a)))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
from operator import itemgetter
from heapq import heapify, heapreplace

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m = list(map(int, read().split()))
    a = [int(i) for i in read().split()]
    bc = sorted([[int(i) for i in read().split()] for _ in range(m)], key=itemgetter(1), reverse=True)
    heapify(a)
    for b, c in bc:
        for _ in range(b):
            if a[0] < c:
                heapreplace(a, c)
            else:
                break
    print((sum(a)))

if __name__ == '__main__':
    main()
# Original solution
import sys
from operator import itemgetter
from heapq import heapify, heapreplace

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m = list(map(int, read().split()))
    a = [int(i) for i in read().split()]
    bc = sorted([[int(i) for i in read().split()] for _ in range(m)], key=itemgetter(1), reverse=True)
    heapify(a)
    for b, c in bc:
        for _ in range(b):
            if a[0] < c:
                heapreplace(a, c)
            else:
                break
    print((sum(a)))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
from operator import itemgetter

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m = list(map(int, read().split()))
    a = sorted(int(i) for i in read().split())
    bc = sorted([[int(i) for i in read().split()] for _ in range(m)], key=itemgetter(1), reverse=True)
    d = []
    for b, c in bc:
        if len(d) < n:
            d += [c] * b
    for i in range(min(n, len(d))):
        if a[i] < d[i]:
            a[i] = d[i]
        else:
            break
    print((sum(a)))

if __name__ == '__main__':
    main()
# Original solution
import sys
from operator import itemgetter

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m = list(map(int, read().split()))
    a = sorted(int(i) for i in read().split())
    bc = sorted([[int(i) for i in read().split()] for _ in range(m)], key=itemgetter(1), reverse=True)
    d = []
    for b, c in bc:
        if len(d) < n:
            d += [c] * b
    for i in range(min(n, len(d))):
        if a[i] < d[i]:
            a[i] = d[i]
        else:
            break
    print((sum(a)))

if __name__ == '__main__':
    main()

# Optimized solution
def main():
    n, m = list(map(int, input().split()))
    a = sorted(int(i) for i in input().split())
    bc = [(0, 0) for _ in range(m)]
    for i in range(m):
        b, c = list(map(int, input().split()))
        bc[i] = (c, b)
    bc.sort(reverse=True)
    k = 0
    d = []
    for c, b in bc:
        if k + b > n:
            d += [c] * (n - k)
            break
        d += [c] * b
        k += b
    for i in range(len(d)):
        if a[i] < d[i]:
            a[i] = d[i]
        else:
            break
    print((sum(a)))


if __name__ == '__main__':
    main()
# Original solution
def main():
    n, m = list(map(int, input().split()))
    a = sorted(int(i) for i in input().split())
    bc = [(0, 0) for _ in range(m)]
    for i in range(m):
        b, c = list(map(int, input().split()))
        bc[i] = (c, b)
    bc.sort(reverse=True)
    k = 0
    d = []
    for c, b in bc:
        if k + b > n:
            d += [c] * (n - k)
            break
        d += [c] * b
        k += b
    for i in range(len(d)):
        if a[i] < d[i]:
            a[i] = d[i]
        else:
            break
    print((sum(a)))


if __name__ == '__main__':
    main()


# Optimized solution
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, m = list(map(int, read().split()))
    a = sorted(int(i) for i in read().split())
    bc = [(0, 0) for _ in range(m)]
    for i in range(m):
        b, c = list(map(int, read().split()))
        bc[i] = (c, b)
    bc.sort(reverse=True)
    k = 0
    d = []
    for c, b in bc:
        if k + b > n:
            d += [c] * (n - k)
            break
        d += [c] * b
        k += b
    for i in range(len(d)):
        if a[i] < d[i]:
            a[i] = d[i]
        else:
            break
    print((sum(a)))


if __name__ == '__main__':
    main()
# Original solution
import heapq
from sys import exit
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: x[1], reverse=True)
heapq.heapify(A)

ans = sum(A)
for b, c in BC:
    for _ in range(b):
        if len(A) == 0:
            print(ans)
            exit()
        a = heapq.heappop(A)
        if a < c:
            ans += c - a
        else:
            print(ans)
            exit()
print(ans)


# Optimized solution
def main():
    import sys
    input = sys.stdin.readline
    N, M = list(map(int, input().split()))
    A = sorted(list(map(int, input().split())))
    BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: x[1], reverse=True)
    ind = 0
    for b, c in BC:
        for i in range(b):
            if ind == N or A[ind] >= c:
                break
            A[ind] = c
            ind += 1
    print((sum(A)))


if __name__ == '__main__':
    main()
# Original solution
import sys
sys.setrecursionlimit(1000000)

from collections import defaultdict

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

dict = defaultdict(int)

for i in range(M):
  B, C = list(map(int, input().split()))
  dict[C] += B

idx = 0
for k, v in sorted(list(dict.items()), key=lambda x: -x[0]):
  for _ in range(v):
    if idx+1 <= len(A):
      if A[idx] < k:
      	A[idx] = k
      	idx += 1
      else:
        print((sum(A)))
        exit()
    else:
      print((sum(A)))
      exit()
      
      
print((sum(A)))


# Optimized solution
N, M = list(map(int, input().split()))
A = sorted([int(i) for i in input().split()])
BC = [tuple(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)

ans = 0
j = 0
b = 0
for i in range(N):
    if j < M and A[i] < BC[j][1]:
        ans += BC[j][1]
        b += 1
        if b == BC[j][0]:
            j += 1
            b = 0
    else:
        ans += A[i]
print(ans)
# Original solution
n,m = list(map(int, input().split()))
a_list = [int(a) for a in input().split()]
a_list.sort()
for i in range(m):
    b,c = list(map(int, input().split()))
    for j in range(b):
        if a_list[j]<c:
            a_list[j] = c
        else:
            break
    a_list.sort()
print((sum(a_list)))

# Optimized solution
n,m = list(map(int, input().split()))
a_list = [int(a) for a in input().split()]
a_list.sort()
bc_list = [0 for _ in range(m)]
for i in range(m):
    b,c = list(map(int, input().split()))
    bc_list[i] = [b,c]
bc_list.sort(key= lambda x:x[1],reverse=True)
cur = 0
for i in range(m):
    b,c = bc_list[i][0],bc_list[i][1]
    for j in range(b):
        if cur >= n:
            break
        if a_list[cur]>=c:
            break
        else:
            a_list[cur] = c
            cur += 1
    else:
        continue
    break
print((sum(a_list)))
# Original solution
#!/usr/bin/env python3
import heapq

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

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

heapq.heapify(a)
for b, c in bc:
    for i in range(b):
        num = heapq.heappop(a)
        if num < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, num)
            break
# print(a)
print((sum(a)))


# Optimized solution
#!/usr/bin/env python3
import heapq

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

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

heapq.heapify(a)
for b, c in bc:
    for i in range(b):
        num = heapq.heappop(a)
        if num < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, num)
            break
# print(a)
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)]

a.sort()
bc.sort(reverse=True, key=lambda x:x[1])
i = 0
ans = []
for b, c in bc:
    N = len(ans)
    for i in range(b):
        if N > n-1: break
        if a[N] < c:
            ans.append(c) 
            N += 1
        else: break
print((sum(ans) + sum(a[len(ans):])))

# 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])
i = 0
ans = 0
for b, c in bc:
    for _ in range(b):
        if i > n-1: break
        if a[i] < c:
            ans += c 
            i += 1
        else: break
print((ans + sum(a[i:])))