ABC 312

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;

    vll need, needless, opener;
    rep(i, N) {
        ll t, x;
        cin >> t >> x;
        if (t == 0) needless.pb(x);
        if (t == 1) need.pb(x);
        if (t == 2) opener.pb(x);
    }

    sort(rall(needless));
    sort(rall(need));
    sort(rall(opener));
    rep(i, (ll)opener.size() - 1) {
        opener[i + 1] += opener[i];
    }
    rep(i, (ll)needless.size() - 1) {
        needless[i + 1] += needless[i];
    }
    rep(i, (ll)need.size() - 1) {
        need[i + 1] += need[i];
    }

    ll ans = 0;
    if (needless.size()) {
        ans = needless[min(M - 1, (ll)needless.size() - 1)];
    }

    rep(i, (ll)need.size()) {
        ll ncan = i + 1;
        if (!opener.size()) break;
        auto it = lower_bound(all(opener), ncan);
        if (it == opener.end()) break;

        // i+1 個の「缶切りが必要な缶」を開けるために必要な缶切りの個数
        ll need_opener = it - opener.begin() + 1;
        if (need_opener + ncan > M) continue;

        ll sum = need[i];
        ll m = M - need_opener - ncan;
        if (m > 0) {  // 缶切り不要な缶が選べる場合、選べるだけ使う
            int id = min(m - 1, (ll)needless.size() - 1);
            sum += needless[id];
        }
        chmax(ans, sum);
    }
    cout << ans << endl;
}