[BOJ 1202] 보석도둑

대략적인 알고리즘은
1. 보석과 가방을 무게 기준으로 정렬
2. 각 가방에 넣을 수 있는 보석 중에서, 가격이 가장 비싼 보석 선택
이다.
N, K <= 300,000이라 $O(NK)$이어서 시간을 줄이는 방법을 고민중이었다.
2단계에서 생각을 해보면 전 가방에 들어갈 수 있는 보석은 당연히 다음 가방에도 들어갈 수 있다. (가방의 무게도 오름차순이므로) 이미 들어간 보석을 다시 확인하는 과정이 필요없다.
그리고 가장 비싼 보석을 선택하려면 다시 정렬해야하는 문제가 있다. 이는 우선순위 큐를 이용하면 가장 비싼 보석을 $O(1)$만에 찾을 수 있다.

1. 보석과 가방 정렬 -> $O(N\log{N}), O(K\log{K})$
2. 가방을 순회 -> $O(K)$
   2.1 각 가방에 우선순위 큐에 보석 가격 삽입 -> $O(\log{N})$

최종 시간복잡도: $\max( O(N\log{N}), O(k\log{K}), O(K\log{N}))$

import sys
sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

import heapq

N, K = map(int, input().split())
jems = []
for _ in range(N):
    m, v = map(int, input().split())
    jems.append([m, v])
bags = []
for _ in range(K):
    bags.append(int(input()))

# 무게를 기준으로 오름차순 정렬
jems.sort()
bags.sort()

pq = []
jem = 0 # 보석 인덱스
answer = 0
for i in range(len(bags)):
    # i번째 가방에 넣을 수 있는 보석 모두 넣기
    # 후보 pq에 넣으면 보석 인덱스 증가
    # pq는 min-heap이므로 (-)를 곱해서 push
    while jem < len(jems) and jems[jem][0] <= bags[i]:
        heapq.heappush(pq, -jems[jem][1])
        jem += 1
    
    # 후보들 중에서 가격이 가장 높은 보석 1개 선택
    if len(pq):
        answer += -heapq.heappop(pq)

print(answer)