CEOI 2011 day 2, hotel

hot.cpp

#include <bits/stdc++.h>

using namespace std;

multiset<pair<int, int>> rooms;
multiset<pair<int, int>, greater<pair<int, int>>> offers;
vector<int> profits;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, o;
	int p, q;
	long long sol = 0;
	
	cin>>n>>m>>o;
	
	while (n--)
	{
		cin>>p>>q;
		rooms.emplace(q, p);
	}
	
	while (m--)
	{
		cin>>p>>q;
		offers.emplace(p, q);
	}
	
	for (auto& offer: offers)
	{
		auto it = rooms.lower_bound({offer.second, 0});
		
		if (it == rooms.end())
			continue;
		
		profits.push_back(offer.first - it->second);
		rooms.erase(it);
	}
	
	sort(profits.begin(), profits.end(), greater<int>());
	
	for (int i = 0; i < o && profits[i] > 0; ++i)
	{
		sol += profits[i];
	}
	
	cout<<sol<<endl;
}