이번 문제는 정렬과 우선순위 큐, 그리디 알고리즘을 활용해 해결하는 문제였다.
본인은 처음에 다음과 같이 생각했다.

• 가방을 내림차순으로 정렬한다.
• 보석의 가치를 내림차순으로 정렬한다.
• 가방의 용량과 보석의 무게를 비교하며 가방에 넣는다.

그러나 이 방법은 만약 보석의 무게와 가치가 (1, 10), (2, 5), (2, 7) 이고 가방의 용량이 1,2라면 용량 2 가방에 (1, 10)이 들어가고 용량 1 가방에는 들어갈 수 있는 보석이 없게되기 때문에 틀린 방법이었다.

그래서 반대로 생각해보았다.

• 가방을 오름차순으로 정렬한다.
• 보석의 무게를 오름차순으로 정렬한다.
• 가방의 용량과 보석의 무게를 비교하여 우선순위 큐에 가능한 보석의 가치를 모두 넣는다.
• 이 과정을 가방의 갯수만큼 반복하고 다음 가방으로 넘어가기 전에 우선순위 큐의 top값을 가치 합에 더해준다.

Code

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 300001
using namespace std;


int n,k;
pair<int, int> jewelry[MAX];
int bag[MAX];
priority_queue<int> pq;
long long sum=0;

void Input(){
    cin>>n>>k;
    for(int i=0; i<n; i++){
        cin>>jewelry[i].first>>jewelry[i].second;
    }
    for(int i=0; i<k; i++){
        cin>>bag[i];
    }
}

void Solution(){
    sort(bag, bag+k);
    sort(jewelry, jewelry+n);
    int idx=0;
    for(int i=0; i<k; i++){
        while(idx<n&&bag[i]>=jewelry[idx].first){
            pq.push(jewelry[idx].second);
            idx++;
        }
        if(!pq.empty()){
            sum+=pq.top();
            pq.pop();
        }
    }
    cout<<sum<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}