Buggy python submission (verdict: Time Limit Exceeded):
import bisect
from operator import itemgetter
n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1))
for i in range(m):
  b, c = BC[i]
  t = bisect.bisect_left(A, c)
  if t > b:
    A = A[b:t] + [c]*b + A[t:]
  else:
    A[:t] = [c]*t
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
from operator import itemgetter
n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1))
for i in range(m):
  b, c = BC[i]
  t = bisect.bisect_left(A, c)
  A[:min(b, t)] = [c]*min(b, t)
  A.sort()
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from operator import itemgetter
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1))
for i in range(m):
  b, c = BC[i]
  for _ in range(b):
    t = heapq.heappop(A)
    heapq.heappush(A, max(c, t))
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from operator import itemgetter
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1))
for i in range(m):
  b, c = BC[i]
  for _ in range(b):
    t = heapq.heappop(A)
    heapq.heappush(A, max(c, t))
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from operator import itemgetter
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1), reverse=True)
for i in range(m):
  b, c = BC[i]
  for _ in range(b):
    t = heapq.heappop(A)
    heapq.heappush(A, max(c, t))
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from operator import itemgetter
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1), reverse=True)
for i in range(m):
  b, c = BC[i]
  for _ in range(b):
    t = heapq.heappop(A)
    heapq.heappush(A, max(c, t))
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
for _ in range(m):
  b, c = map(int, input().split())
  for i in range(b):
    t = heapq.heappop(A)
    heapq.heappush(A, max(c, t))
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
for _ in range(m):
  b, c = map(int, input().split())
  for i in range(b):
    t = heapq.heappop(A)
    heapq.heappush(A, max(c, t))
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = [ list(map(int, input().split())) for _ in range(m) ]
BC.sort(key=lambda x:x[1], reverse=True)
for b, c in BC:
  d = bisect.bisect_left(A, c)
  t = min(d, b)
  for i in range(t):
    A[i] = c
  if b >= d:
    print(sum(A))
    exit()
  else:
    A = A[b:d] + A[:b] + A[d:]
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = [ list(map(int, input().split())) for _ in range(m) ]
BC.sort(key=lambda x:x[1], reverse=True)
for b, c in BC:
  d = bisect.bisect_left(A, c)
  t = min(d, b)
  for i in range(t):
    A[i] = c
  if b >= d:
    print(sum(A))
    exit()
  else:
    A = A[b:d] + A[:b] + A[d:]
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = [ list(map(int, input().split())) for _ in range(m) ]
for b, c in BC:
  d = bisect.bisect_left(A, c)
  t = min(d, b)
  A = A[t:d] + [c]*t + A[d:]
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = [ list(map(int, input().split())) for _ in range(m) ]
for b, c in BC:
  d = bisect.bisect_left(A, c)
  t = min(d, b)
  A = A[t:d] + [c]*t + A[d:]
print(sum(A))

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

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = [ list(map(int, input().split())) for _ in range(m) ]
for b, c in BC:
  d = bisect.bisect_left(A, c)
  t = min(d, b)
  for i in range(t):
    A[i] = c
  if t == b:
    A = A[b:d] + A[:b] + A[d:]
print(sum(A))


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

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = [ list(map(int, input().split())) for _ in range(m) ]
for b, c in BC:
  d = bisect.bisect_left(A, c)
  t = min(d, b)
  for i in range(t):
    A[i] = c
  if t == b:
    A = A[b:d] + A[:b] + A[d:]
print(sum(A))

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