#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <limits.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <numeric> #include <deque> #include <bitset> #include <iostream> using namespace std; typedef long long lint; typedef long double llf; typedef pair<int, int> pi; int n, m, s; pi a[300005]; multiset<pi> lev1, lev2; int main(){ cin >> n >> m >> s; for(int i=0; i<n; i++){ scanf("%d %d",&a[i].first, &a[i].second); } sort(a, a+n); reverse(a, a+n); lint ret = 0; for(int i=0; i<m; i++){ ret += a[i].first; lev2.insert(pi(a[i].first, a[i].second)); } for(int i=m; i<n; i++){ lev1.insert(pi(a[i].first, a[i].second)); } for(int i=0; i<s; i++){ int prof1 = -1e9, prof2 = -1e9, prof3 = -1e9; int add1 = 1e9, add2 = 1e9; pi pp1, pp2, pp3; for(auto &i : lev1){ if(prof1 < i.second){ prof1 = i.second; pp1 = i; } if(prof2 < i.first){ prof2 = i.first; pp2 = i; } } for(auto &i : lev2){ if(prof3 < i.second - i.first){ prof3 = i.second - i.first; pp3 = i; } } if(prof1 >= prof2 + prof3){ ret += prof1; lev1.erase(lev1.find(pp1)); } else{ ret += prof2 + prof3; lev2.erase(lev2.find(pp3)); lev2.insert(pp2); lev1.erase(lev1.find(pp2)); } // case 1. get s from empty set // case 2. get s from nonempty + get m from empty // case 3. swap s from empty set } cout<< ret; }