3つタイプがあるが，いずれも貪欲に取れる． どれか一つを全探索しよう． 缶切りを使わない缶全体， 缶切りを使う缶全体， 缶切り全体 をそれぞれ \(a,b,c\) とおく． \(a,b,c\) を全てソートしておく．
\(a\) を全探索する． \(i \in size(a)\) に対して，\([0,i)\) まで使ったとする． このとき，\(b,c\) からどちらを選ぶべきかは貪欲に決まる．
缶切りが残っていれば \(b\) から買えばよい． 残ってなければ，\(c\) から買って缶切りを補充． 実装するときは，\(b,c\) が空になる場合に注意．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n >> m;
vvll a(3);
rep(i,n){
ll t, x; cin >> t >> x;
a[t].push_back(x);
}
sort(all(a[0]), greater<ll>());
sort(all(a[1]));
sort(all(a[2]));
vvll s(2, vll(n+1));
ll r = 0;
rep(i,n) {
if(i < a[0].size()) s[0][i+1] = s[0][i] + a[0][i];
else s[0][i+1] = s[0][i];
ll now = 0;
if(r){
--r;
if(a[1].size()){
now = a[1].back();
a[1].pop_back();
}
}else if(a[2].size()){
r += a[2].back();
a[2].pop_back();
}
s[1][i+1] = s[1][i] + now;
}
ll ans = -INFL;
rep(i,m+1) chmax(ans, s[0][i] + s[1][m-i]);
cout << ans << endl;
return 0;
}
