백준/python 1202 보석 도둑

import sys
import heapq

input = sys.stdin.readline

n, k = map(int, input().split())
gems = []
for _ in range(n):
  heapq.heappush(gems, list(map(int, input().split())))

bags = []
for _ in range(k):
  bags.append(int(input()))
bags.sort()

q = []
answer = 0
for bag in bags:
  while gems and bag >= gems[0][0]: 
	# 모든 보석을 찾는데 각 보석의 무게가 배낭의 용량을 넘지 않을 때 배낭에 넣기
    heapq.heappush(q, -heapq.heappop(gems)[1])
    # 탐색한 보석들을 계속 넣어주는데 결국 최종적으로 가치가 가장 높은 보석을 찾아야 한다.

  if q:
    answer -= heapq.heappop(q)
    # q를 새로 초기화하지 않고 heapop만 계속 해주는 이유는
    # 보석과 가방을 무게순으로 정렬하고 탐색하고 있기 때문에 이미 더 가벼운 가방에
    # 들어갈 수 있는 보석이면 무거운 가방에도 당연히 들어갈 수 있기 때문에 초기화를 하지 않는다.


print(answer)