가방 K개가 주어질 때, 하나의 가방에는 정해진 무게까지의 보석만 담을 수 있다. 그렇다면 보석 N개를 가방 K개에 담아서 훔칠 수 있다면 훔친 보석 가격이 최대가 되게 만들어야 한다.
보석 N개를 무게 순으로 오름차순 정렬하고, 가방도 담을 수 있는 무게에 따라서 오름차순 정렬한다. 보석의 가격이 최대가 되기 위해선 가방에 담을 수 있는 보석중에서 가장 비싼 보석을 담으면 된다. 이 때 가방을 기준으로 가장 작은 무게를 담을 수 있는 가방부터 탐색하게 되는데, 이유는 다음과 같은 반례로 예를 들 수 있다.
ex)
보석 1: 무게 1, 가격 99
보석 2: 무게 99 가격 1
가방 - 1, 99
의 경우 무거운 가방 순서로 탐색을 하면 99에 가장 비싼 보석(보석 1)을 담고, 그 다음 1짜리 가방에는 아무것도 담지 못해서 총 가격 99가 된다.
하지만 가벼운 가방 순서로 탐색을 하면 1에 가장 비싼 보석(보석 1)을 담고, 그다음 99짜리 가방에 무게 99짜리 보석(보석 2)을 담아서 총 가격은 100이 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// 보석 행렬
public static int[][] acce;
// 가방은 벡터 어레이로
public static ArrayList<Integer> bag;
// 최대 힙으로 쓸 녀석
public static PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
acce = new int[N][2];
bag = new ArrayList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
acce[i][0] = Integer.parseInt(st.nextToken());
acce[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(acce, (o1, o2) -> {
if(o1[0] == o2[0]) return Integer.compare(o1[1], o2[1]);
else return Integer.compare(o1[0], o2[0]);
});
for (int i = 0; i < K; i++) {
bag.add(Integer.parseInt(br.readLine()));
}
bag.sort(Comparator.naturalOrder());
long result = 0;
int idx = 0;
for(int i = 0; i < K; i++) {
int M = bag.get(i);
while(idx < N && acce[idx][0] <= M) {
queue.add(acce[idx][1]);
idx++;
}
if (queue.size() != 0) {
result = (long) result + queue.poll();
}
}
System.out.print(result);
br.close();
}
}