CodeEff/ECCO huggingface dataset:
# Original solution
N, M = list(map(int, input().split()))

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

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

A.sort()
B.sort(reverse=True)
for i in range(min(N, len(B))):
    if A[i] < B[i]:
        A[i] = B[i]

ans = sum(A)
print(ans)

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

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

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

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

count = 0
CArr = []
for b, c in BC:
    if count >= N:
        break
    for i in range(b):
        CArr.append(c)
        count += 1
        if count >= N:
            break

for i in range(len(CArr)):
    if A[i] < CArr[i]:
        A[i] = CArr[i]

ans = sum(A)
print(ans)
# Original solution
n,m = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort()
B=[]
C=[]
for i in range(m):
  b,c = list(map(int,input().split()))
  B.append(b)
  C.append(c)
L = list(zip(C,B))
L.sort(reverse = True)
L2 = []
for i in range(m):
  L2.extend([L[i][0]]*L[i][1])
#print(L2)
ans = 0
for i in range(n):
  if i >= len(L2): ans+=A[i]
  else:
    if L2[i] > A[i]:ans+=L2[i]
    else: ans+=A[i]
print(ans)

# Optimized 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()))
  A.extend([c for j in range(b)])
A.sort(reverse=True)
print((sum(A[:n])))
# 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()))
  A.extend([c for j in range(b)])
A.sort(reverse=True)
print((sum(A[:n])))

# Optimized solution
n,m = list(map(int,input().split()))
A = list(map(int,input().split()))
CntA = [1 for i in range(n)]
for i in range(m):
  b,c = list(map(int,input().split()))
  A.append(c)
  CntA.append(b)
Z = list(zip(A,CntA))
Z.sort(reverse=True)
ans = 0
for z in Z:
  if n>z[1]:
    ans+=z[1]*z[0]
    n-=z[1]
  else:
    ans+=n*z[0]
    break
print(ans)
# Original solution
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    x = [[B[i],C[i]] for i in range(M)]
    x = sorted(x, key=lambda x:x[1], reverse=True)

    D = []
    for i in range(M):
        D.extend([x[i][1]]*x[i][0])


    A.sort()

    for i in range(min(N, len(D))):
        if(A[i] < D[i]):
            A[i] = D[i]

    print((sum(A)))

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()


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


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    x = [[B[i],C[i]] for i in range(M)]
    x = sorted(x, key=lambda x: -x[1])

    A.sort()

    dn = 0
    for b, c in x:
        for j in range(b):
            if(dn >= N):
                break
            if(A[dn] < c):
                A[dn] = c
                dn += 1
            else:
                break


    print((sum(A)))

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()
# Original solution
import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
B, C = list(zip(*[list(map(int, input().split())) for _ in range(M)]))

heap = A
heapq.heapify(heap)


for b, c in zip(B, C):
    for _ in range(b):
        if heap[0] < c:
            heapq.heapreplace(heap, c)
        else:
            break

print((sum(heap)))


# Optimized solution
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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

A.sort()
CB.sort()

ans = 0
for _ in range(N):
    a = A[-1] if A else -INF
    c, b = CB[-1] if CB else (-INF, -INF)
    if a > c:
        ans += a
        A.pop()
    else:
        ans += c
        CB[-1][1] -= 1
        if CB[-1][1] <= 0:
            CB.pop()
print(ans)
# Original solution
from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
for i in range(M):
    A = A + [BC[i][1]] * BC[i][0]
    if len(A) >= 2 * N:
        break

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


# Optimized solution
from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
for i in range(M):
    A.extend([BC[i][1]] * BC[i][0])
    if len(A) >= 2 * N:
        break

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

index = 0
for i in range(len(BC)):
    for j in range(BC[i][0]):
        if index == len(A) or A[index] >= BC[i][1]:
            break

        else:
            A[index] = BC[i][1]
            index += 1

print((sum(A)))
    

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

index = 0
l = len(A)

for i in range(len(BC)):
    for j in range(BC[i][0]):
        if index == l or A[index] >= BC[i][1]:
            break
        else:
            A[index] = BC[i][1]
            index += 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()))[::-1]for _ in range(M)]

L=[0]
for c,b in BC:
    L+=[c]*b

ans=sorted(A+L)[::-1]
print((sum(ans[:N])))

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

L=[0]
for c,b in BC:
    L+=[c]*b
    if len(L)-1>N:
        break

ans=sorted(A+L)[::-1]
print((sum(ans[:N])))
# Original solution
from collections import defaultdict

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

numCnt = defaultdict(int)

for a in A:
    numCnt[a] += 1

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

ans = 0
numList = list(numCnt.items())
numList.sort(reverse=True)

for num, cnt in numList:
    while N > 0 and cnt > 0:
        ans += num
        N -= 1
        cnt -= 1

print(ans)

# Optimized solution
from collections import Counter
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

cntA = Counter(A)
for _ in range(M):
    B, C = list(map(int, input().split()))
    cntA[C] += B

ans = 0
for val, cnt in sorted(list(cntA.items()), reverse=True):
    ans += val * min(N, cnt)
    N -= cnt
    if N <= 0:
        break
print(ans)
# Original solution
import bisect

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

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

nums.sort()

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

total = 0
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if c < nums[0]:
        break
    if total > n:
        break

    index = bisect.bisect_left(nums, c)
    if index > 0:
        temp = nums[0:index]
        temp.extend([c]*b)
        temp.extend(nums[index:])
        nums = temp[-n:]
    total = total + b
print((sum(nums)))

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

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

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

total = 0
sums = []
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if total > n:
        break
    sums.extend([c]*b)
    total = total + b
print((sum(sums[:n])))
# Original solution
import sys
# sys.setrecursionlimit(100000)
import heapq


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(eval(input()))


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import Counter
    n, m = input_int_list()
    hq = list(Counter(input_int_list()).items())

    heapq.heapify(hq)

    for _ in range(m):
        b, c = input_int_list()
        while b > 0:
            k, v = heapq.heappop(hq)
            if k >= c:
                heapq.heappush(hq, (k, v))
                break
            else:
                if v == b:
                    heapq.heappush(hq, (c, b))
                    b = 0
                elif v > b:
                    heapq.heappush(hq, (c, b))
                    heapq.heappush(hq, (k, v - b))
                    b = 0
                elif b > v:
                    heapq.heappush(hq, (c, v))
                    b -= v
    ans = 0
    for k, v in hq:
        ans += k * v

    print(ans)

    return


if __name__ == "__main__":
    main()


# Optimized solution
import sys
# sys.setrecursionlimit(100000)
import heapq


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(eval(input()))


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import Counter
    # 計算量 O(n*log_n + m*log_m)

    # 入力
    n, m = input_int_list()
    hq = list(Counter(input_int_list()).items())  # O(n)
    # 最小値管理にPriorityQueueを使う

    heapq.heapify(hq)  # O(n*log_n)

    queries = []
    for _ in range(m):
        queries.append(input_int_list())

    queries.sort(key=lambda x: x[1], reverse=True)  # O(m * log_m)

    # cが大きい数字から処理したほうが効率的になる
    for b, c in queries:
        while b > 0:
            k, v = heapq.heappop(hq)
            if k >= c:
                heapq.heappush(hq, (k, v))
                break
            else:
                if v == b:
                    heapq.heappush(hq, (c, b))
                    b = 0
                elif v > b:
                    heapq.heappush(hq, (c, b))
                    heapq.heappush(hq, (k, v - b))
                    b = 0
                elif b > v:
                    heapq.heappush(hq, (c, v))
                    b -= v
    ans = 0
    for k, v in hq:
        ans += k * v

    print(ans)

    return


if __name__ == "__main__":
    main()
# Original solution
import collections
n, m = [ int(v) for v in input().split() ]
num_list = [ int(v) for v in input().split() ]
total_counter = collections.Counter([])

for i in range(m):
    b, c =  [ int(v) for v in input().split() ]
    total_counter[c] += b
for i in num_list:
    total_counter[i] += 1


total_counter_2 = list(zip(list(total_counter.keys()), list(total_counter.values())))

ans_list = []
c = 0
for i in sorted(total_counter_2,reverse = True):
    p, q = i
    for j in range(q):
        ans_list.append(p)
    c += q
    if c >= n:
        break
print((sum(ans_list[:n])))


# Optimized solution
import sys
input = sys.stdin.readline

def swap(a):
    return ((a[1],a[0]))


n, m = [ int(v) for v in input().split() ]
num_list = [ (int(v), 1) for v in input().split() ]
change_list = [ swap([ int(v) for v in input().split() ]) for i in range(m) ]
total_list = sorted(num_list + change_list, reverse = True)

k = n
ans = 0

for i in total_list:

    j = min(i[1], k)
    k -= j
    ans += i[0] * j
    if k == 0:
        break
print(ans)
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
from bisect import bisect_left
b = []
for i in range(m):
  b.append(list(map(int, input().split())))
b.sort(key=lambda x: x[1], reverse=True)
cur = 0
ans = 0
for e in b:
  t = bisect_left(a[cur:], e[1])
  ans += min(t, e[0])*e[1]
  cur += min(t, e[0])
while cur<len(a):
  ans += a[cur]
  cur += 1
print(ans)

# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
from bisect import bisect_left
b = [list(map(int, input().split())) for i in range(m)]
b.sort(key=lambda x: x[1], reverse=True)
cur = 0
ans = 0
for e in b:
  t = bisect_left(a, e[1])
  if t>=cur:
    ans += min(t-cur, e[0])*e[1]
    cur += min(t-cur, e[0])
while cur<len(a):
  ans += a[cur]
  cur += 1
print(ans)
# Original solution
from sys import stdin
N,M=[int(x) for x in stdin.readline().rstrip().split()]
A=[int(x) for x in stdin.readline().rstrip().split()]
data=[]
A = sorted(A)
for i in range(M):
    r,q=[int(x) for x in stdin.readline().rstrip().split()]
    if q >= A[0]:
        for j in range(r):
            A.append(q)
 
ans = sum(sorted(A)[::-1][:N])
print(ans)

# Optimized solution
from sys import stdin
N,M=[int(x) for x in stdin.readline().rstrip().split()]
A=[(int(x),1) for x in stdin.readline().rstrip().split()]
data=[]
for i in range(M):
    r,q=[int(x) for x in stdin.readline().rstrip().split()]
    A.append((q,r))
ans=0
cnt=0
for j in reversed(sorted(A)):
    cnt+=j[1]
    ans+=(j[0]*j[1])
    if cnt > N:
        ans = ans-(j[0]*(cnt-N))
        break
print(ans)
# 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() ))
  a += [ c ] * b
 
a.sort()
print((sum(a[-N:])))

# Optimized 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 += [ c ] * b
  d.sort()
a += d
a.sort()
print((sum(a[-N:])))
# Original solution
n, m = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
bc = [list(map(int, input().split())) for _ in range(m)]

for i in range(m):
    listnum=bc[i][0]
    tplist=[bc[i][1]]
    templist=tplist*listnum
    a.extend(templist)
a=sorted(a,reverse=True)
print((sum(a[:n])))


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

[a.extend([bc[i][1]]*bc[i][0]) for i in range(m)]

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

[a.extend([bc[i][1]]*bc[i][0]) for i in range(m)]

print((sum(sorted(a,reverse=True)[: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)]

sorted_ab=sorted(bc, reverse=True, key=lambda x: x[1])
new_ab=[]
ans=[]

for i in range(m):
    if len(new_ab)<=n:
        tmp_l=[sorted_ab[i][1]]*sorted_ab[i][0]
        new_ab+=tmp_l
    else:
        break

final_list=a+new_ab
final_list.sort(reverse=True)

print((sum(final_list[:n])))
# Original solution
import sys
from bisect import bisect_left
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = sorted([int(x) for x in input().strip().split()])
BC = [0] * M

for m in range(M):
    BC[m] = tuple([int(x) for x in input().strip().split()])

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

offset = 0
ans = 0
for i, bc in enumerate(BC):
    if offset >= len(A):
        break
    if bc[1] >= A[min(offset+bc[0]-1, len(A)-1)]:
        ans += min(bc[0], len(A[offset:])) * bc[1]
        offset += bc[0]
        continue
    elif bc[1] <= A[offset]:
        ans += sum(A[offset:])
        break
    else:
        c = 0
        while bc[1] >= A[offset+c]:
            ans += bc[1]
            c += 1
        else:
            offset += c
else:
    if offset < len(A):
        ans += sum(A[offset:])
print(ans)

# Optimized solution
import sys
from bisect import bisect_left
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = sorted([int(x) for x in input().strip().split()])
BC = [0] * M

for m in range(M):
    BC[m] = tuple([int(x) for x in input().strip().split()])

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

offset = 0
ans = 0
for i, bc in enumerate(BC):
    if offset >= len(A):
        break
    if bc[1] >= A[min(offset+bc[0]-1, len(A)-1)]:
        ans += min(bc[0], N - offset) * bc[1]
        offset += bc[0]
        continue
    elif bc[1] <= A[offset]:
        ans += sum(A[offset:])
        break
    else:
        c = 0
        while bc[1] >= A[offset+c]:
            ans += bc[1]
            c += 1
        else:
            offset += c
else:
    if offset < len(A):
        ans += sum(A[offset:])
print(ans)
# Original solution
n,m = list(map(int,input().split()))
bc = {}
a = list(input().split())
for i in a:
  if i in bc:
    bc[i] += 1
  else:
    bc[i] = 1
for i in range(m):
  b,c = input().split()
  b = int(b)
  if c in bc:
    bc[c] += b
  else:
    bc.update({c:b})
key = sorted(bc)
for k in range(len(key)):
  key[k] = int(key[k])
key.sort()
key.reverse()
for k in range(len(key)):
  key[k] = str(key[k])
c = 0
s = 0
for i in key:
  if i in bc:
    s += int(i) * bc[i]
    c += bc[i]
    if c > n:
      s -= int(i) * (c-n)
      c -= c-n
  if c == n:
    break
print(s)

# Optimized 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 = sorted(bc,key=lambda x:x[1])
bc.reverse()
count = 0
for b,c in bc:
  count += b
  a += [c] * b
  if count >= n:
    break
a.sort()
a.reverse()
print((sum(a[:n])))
# 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 = sorted(bc,key=lambda x:x[1])
bc.reverse()
count = 0
for b,c in bc:
  count += b
  a += [c] * b
  if count >= n:
    break
a.sort()
a.reverse()
print((sum(a[:n])))

# Optimized solution
import sys

def main():
  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 = sorted(bc,key=lambda x:x[1])
  bc.reverse()
  count = 0
  for b,c in bc:
    count += b
    a += [c] * b
    if count >= n:
      break
  a.sort()
  a.reverse()
  return sum(a[:n])

if __name__ == '__main__':
  print((main()))
# Original solution
n,m = list(map(int,input().split()))

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

min_a = min(a)

bc = []
for _ in range(m):
    b, c = (int(x) for x in input().split())
    bc.append([b,c])

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

memo = []

limit = 0

for i in range(m):
    a = a + [bc[i][1]]*bc[i][0]
    limit += bc[i][0]
    if limit >= n or min_a >= bc[i][1]:
        break

a.sort(reverse=True)

ans = 0

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

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

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

bc = []
for _ in range(m):
    b, c = (int(x) for x in input().split())
    bc.append([b,c])

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

memo = []

limit = 0

for i in range(m):
    a += [bc[i][1]]*bc[i][0]
    limit += bc[i][0]
    if limit >= n:
        break

a.sort(reverse=True)

print((sum(a[:n])))
# Original solution
import heapq

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

a = list(map(int,input().split()))
bc = []
for _ in range(m):
    b, c = (int(x) for x in input().split())
    bc.append([b, c])
bc = sorted(bc, key=lambda x: -x[1])

heapq.heapify(a)

for i in range(m):
    count = 0
    if bc[i][1] < a[0]:
        break
    while a[0] < bc[i][1] and count < bc[i][0]:
        heapq.heappop(a)
        heapq.heappush(a,bc[i][1])
        count += 1
print((sum(a)))

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

A = list(map(int,input().split()))
A.sort(reverse=True)
BC = []
for _ in range(M):
    B, C = (int(x) for x in input().split())
    BC.append([B, C])
BC = sorted(BC, key=lambda x: -x[1])

index = 0

ans = 0

while index < M and len(A) and A[-1] < BC[index][1]:
    b, c = BC[index]
    count = 0
    while len(A) and A[-1] < c and count < b:
        A.pop()
        ans += c
        count += 1
    index += 1
print((sum(A)+ans))
# Original solution
import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [0]*m
c = [0]*m
sortsecond = lambda val: val[1]

x = [list(map(int, input().split())) for _ in range(m)]
x.sort(key=sortsecond)

for j in range(m):
    times = x[-(j+1)][0]
    number = x[-(j+1)][1]
    while times > 0 :

        temp = min(a)
        if temp < number:
            a[a.index(temp)] = number
        else:
            break
        times -= 1


print((sum(a)))

# Optimized solution
import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [0]*m
c = [0]*m
sortsecond = lambda val: val[1]

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

x.sort(key=sortsecond)

a.sort()


i = 0
for j in range(m):
    times = x[-(j+1)][0]
    number = x[-(j+1)][1]
    while times > 0 :

        try:
            temp = a[i]
        except IndexError:
            print((sum(a)))
            exit()
        
        if temp < number:
            a[i] = number
        else:
            print((sum(a)))
            exit()
        times -= 1
        i += 1
print((sum(a)))
# Original solution
from heapq import heapify, heapreplace
N,M=[int(a) for a in input().split()]
A=[int(a) for a in input().split()]
BC=[[int(a) for a in input().split()] for _ in range(M)]
heapify(A)
for B,C in BC:
    for _ in range(B):
        if C<=A[0]:
            break
        heapreplace(A, C)
print((sum(A)))

# Optimized solution
from heapq import heapify, heapreplace
N,M=[int(a) for a in input().split()]
A=sorted([int(a) for a in input().split()])
BC=[[int(a) for a in input().split()] for _ in range(M)]
B,C=list(zip(*sorted(BC, key=lambda row: row[1], reverse=True)))
i,j=0,0
for k in range(N):
    if j>=B[i]:
        i+=1
        j=0
    if i>=M or A[k]>= C[i]:
        break
    A[k] = C[i];
    j+=1
print((sum(A)))