If we fix the number of pull-tab cans, it is obviously optimal to choose cans with greater happiness.
Similarly, if we fix the number of regular cans, it is optimal to choose cans with greater happiness; regarding can openers, it is optimal to choose those that can open more cans.
By sorting them in descending order and taking sums, we can find for each \(t\) the maximum happiness when choosing \(t\) pull-tab cans. Therefore, it is sufficient to know for each \(s\) the maximum happiness when choosing \(s\) regular cans and can openers in total.
Here, in an optimal solution, we can assume that there is no regular can against which a can opener is unused, and no can opener that is not used against any cans, so the following greedy procedure yields an optimal solution:

• If there remains a usable can opener, choose a regular can with the maximum happiness.
• Otherwise, choose a can opener that can open the maximum number of cans.

By sorting the happinesses of the regular cans and the number of times that can openers can be used, the greedy runs in a total of \(O(N)\) time, so the problem has been solved.

Sample code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }

int main() {
	ll n, m;
	cin >> n >> m;
	vector<ll> a, b, c;
	for (int i = 0; i < n; i++) {
		int t; ll x;
		cin >> t >> x;
		if (t == 0) a.push_back(x);
		else if (t == 1) b.push_back(x);
		else c.push_back(x);
	}
	sort(a.begin(), a.end(), greater<>());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());
	vector<ll> x(n + 1), y(n + 1);
	for (int i = 0; i < n; i++) {
		if (i < a.size()) x[i + 1] = x[i] + a[i];
		else x[i + 1] = x[i];
	}
	int r = 0;
	for (int i = 0; i < n; i++) {
		if (b.empty()) y[i + 1] = y[i];
		else if (r == 0) {
			if (!c.empty()) {
				r += c.back();
				c.pop_back();
			}
			y[i + 1] = y[i];
		}
		else {
			r--;
			y[i + 1] = y[i] + b.back();
			b.pop_back();
		}
	}
	ll ans = 0;
	for (int i = 0; i <= m; i++) chmax(ans, x[i] + y[m - i]);
	cout << ans << endl;
}