abc 127 D - Integer Cards (python)

A の小さいものを Ci のうち一番大きいものに変えていくのが一番大きくなるなあと考えた。
大きいものから変えていくので、N枚変える or Aの最小値が現在の Ci 以上になったらそこで終了してよい。
最小値を取り出すのを heapq で高速化
値の変更がなくても heappop で取り出したものを heappush で再び入れなおす必要があることに注意。
itemgetter で多次元ソートと heapq で最小値や最大値を取り出すの頻繁に使っている気がする。
あとは bisect かな

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n,m = map(int,readline().split())
a = list(map(int,readline().split()))
import heapq
heapq.heapify(a)

b = []
for i in range(m):
  c = list(map(int,readline().split()))
  b.append(c)
  
from operator import itemgetter
b = tuple(sorted(b,key=itemgetter(1),reverse=True))

cnt = 0
for i in b:
  cnt += i[0]
  chk = i[0]
  for j in range(chk):
    p = heapq.heappop(a)
    if p >= i[1]:
      cnt += 10**5
      heapq.heappush(a,p)
      break
    heapq.heappush(a,i[1])
  if cnt >= n:
    break
print(sum(a))