给牛和草都按价格排序,然后贪心地把草给牛(就是尽量给满足价格的、要求的美味度最高但不超过这个草的美味度的牛)
这个可以用一个平衡树来维护,偷懒直接用multiset了
#include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxn=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} multiset<int> st;
int N,M;
pa cow[maxn],gra[maxn]; int main(){
//freopen("1691.in","r",stdin);
int i,j,k;
N=rd();M=rd();
for(i=;i<=N;i++){
cow[i].first=rd(),cow[i].second=rd();
}for(i=;i<=M;i++){
gra[i].first=rd(),gra[i].second=rd();
}
sort(cow+,cow+N+);sort(gra+,gra+M+);
ll ans=;int num=;
for(i=,j=;i<=M&&num<=N;i++){
//printf("%d %d\n",i,j);
for(;cow[j].first<=gra[i].first&&j<=N;j++){
st.insert(cow[j].second);
}
if(st.empty()||(*st.begin())>gra[i].second) continue;
multiset<int>::iterator it=st.upper_bound(gra[i].second);it--;
//printf("%d %d %d %d\n",gra[i].first,gra[i].second,*it,it==st.end());
st.erase(it);ans+=gra[i].first;num++;
}
if(num==N) printf("%lld\n",ans);
else printf("-1\n");
return ;
}