보석도둑

 

비싼 보석일수록 우선도가 높으며, 이를 넣을 수 있는 가방이 존재하는지를 확인하기만 하면 되기에,

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <functional>
 
#define MAXX 300001
 
using namespace std;
 
typedef pair<int, int> pp;
typedef long long ll;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, k;
 
    cin >> n >> k;
 
    // vector<pp> jewels;
    multiset<pp, greater<pp> > ms;
    multiset<pp>::iterator it;
    for (int i = 0; i < n; i++)
    { //o(n)
        int m, v;
        cin >> m >> v;
 
        ms.insert(pp(v, m));
    }
 
    // for (it = ms.begin(); it != ms.end(); it++) cout << it->second << " " << it->first << '\n';
    ll sum = 0;
    //o(k)
    multiset<int> bag;
    multiset<int>::iterator idx;
 
    for (int i = 0; i < k; i++)
    {
        int c;
        cin >> c;
 
        //각 가방마다 최대 들 수 있는 무게 중 최대값을 찾아서 더한다.
        //o(nlogn)
        bag.insert(c);
    }
 
    for (it = ms.begin(); it != ms.end()&&!bag.empty(); it++)
    {
        idx = bag.lower_bound(it->second);
        if (idx != bag.end())
        {
            sum += it->first;
            bag.erase(idx);
        }
      
    }
 
    cout << sum << '\n';
    return 0;
}