解法

概要

答え を二分探索。 のbitを小さい側から見ながら貪欲。 計算量は

詳細

答え が既知としたとき、次のようにすればよい:

  1. の1bit目が1なら であるような宿題 のなかで を最大にするものを使う
  2. であるような宿題 でまだ使われてないものを の順で貪欲にふたつずつ組にし のようにして の宿題であったことにする
  3. の2bit目が1なら であるような宿題 のなかで を最大にするものを使う
  4. であるような宿題 でまだ使われてないものを の順で貪欲にふたつずつ組にし のようにして の宿題であったことにする
  5. の2bit目が3なら であるような宿題 のなかで を最大にするものを使う

この貪欲が最適なのは明らか。 単純に見ると長さ の列に対するソートなどの操作を 回行なうことになる。 しかし長さは毎回半分になることから 回の長さの合計は を越えず、 を固定するごとに で済む。 と仮定すると全体の計算量は

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
    assert (l <= r);
    -- l;
    while (r - l > 1) {
        int64_t m = l + (r - l) / 2;
        (p(m) ? r : l) = m;
    }
    return r;
}

constexpr int L = 60;
ll solve(int n, ll k, vector<int> const & a, vector<ll> const & b) {
    vector<vector<ll> > f(L);
    REP (i, n) {
        f[a[i]].push_back(b[i]);
    }
    REP (i, L) {
        sort(ALL(f[i]));
    }
    return binsearch(0, 1ll << L, [&](ll sum_a) {
        ll sum_b = 0;
        vector<ll> cur, prv;
        REP (i, L) {
            cur.insert(cur.end(), ALL(f[i]));
            if (cur.empty()) continue;
            sort(ALL(cur));
            if (sum_a & (1ll << i)) {
                sum_b += cur.back();
                cur.pop_back();
            }
            cur.swap(prv);
            cur.clear();
            while (not prv.empty()) {
                int k = prv.size();
                if (k == 1) {
                    cur.push_back(prv[k - 1]);
                    prv.pop_back();
                } else {
                    cur.push_back(prv[k - 1] + prv[k - 2]);
                    prv.pop_back();
                    prv.pop_back();
                }
            }
        }
        return k <= sum_b;
    });
}

int main() {
    int n; ll k; cin >> n >> k;
    vector<int> a(n);
    vector<ll> b(n);
    REP (i, n) cin >> a[i] >> b[i];
    cout << solve(n, k, a, b) << endl;
    return 0;
}