缶切りが不要な缶を選ぶ個数を固定すると、明らかに満足度が大きいものから選ぶのが最適です。
同様に、缶切りが必要な缶についても選ぶ個数を固定すると満足度が大きいものから選ぶのが最適で、缶切りについても使用できる缶の個数が多いものから選ぶのが最適です。
降順にソートして和を取ることで、各 \(t\) について缶切りが不要な缶を \(t\) 個選ぶときに得られる満足度の最大値がわかります。 したがって、各 \(s\) について缶切りが必要な缶と缶切りを合計 \(s\) 個選ぶときに得られる満足度の最大値がわかればよいです。
ここで、最適解において缶切りが必要な缶であって、缶切りが使用されないものと、缶切りであって、どの缶に対しても使用しないものが存在しないとしてよいことから、以下のような貪欲により最適解が得られることがわかります。

• まだ使用できる缶切りがあるならば、缶切りが必要な缶であって、満足度が最大のものを選ぶ。
• そうでないならば、缶切りであって、使用できる缶の個数が最大のものを選ぶ。

あらかじめ缶切りが必要な缶の満足度と缶切りの使用できる回数をソートしておくことで、上で示した貪欲は \(O(N)\) で行え、この問題が解けました。

実装例

#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;
}