半分全列挙

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    ll W;
    cin >> N >> W;
    for (int i = 0; i < N; i++) cin >> v[i] >> w[i];
    if (N <= 30) {
        int n = N/2;
        for (int i = 0; i < 1<<n; i++) {
            ll sw = 0, sv = 0;
            for (int j = 0; j < n; j++) {
                if ((i>>j)&1) {
                    sw += w[j];
                    sv += v[j];
                }
            }
            ps[i] = pll(sw, sv);
        }
        sort(ps, ps+(1<<n));
        int m = 1;
        for (int i = 1; i < 1<<n; i++) {
            if (ps[m-1].second < ps[i].second) ps[m++] = ps[i];
        }
        ll res = 0;
        for (int i = 0; i < 1<<(N-n); i++) {
            ll sw = 0, sv = 0;
            for (int j = 0; j < N-n; j++) {
                if ((i>>j)&1) {
                    sw += w[n+j];
                    sv += v[n+j];
                }
            }
            if (sw <= W) {
                ll tv = (lower_bound(ps, ps+m, make_pair(W-sw, 1ll<<55))-1)->second;
                res = max(res, sv+tv);
            }
        }
        cout << res << endl;
        return 0;
    }
}

lines = $stdin.read
array = lines.split("\n")
N,W  = array[0].split(" ").map(&:to_i)
item = array[1..N+1].map do |str|
  str.split(" ").map(&:to_i)
end

exit 0 if N>30

tmp_h = {}
tmp_a = []

s = 0
S1 = item[0...N/2]
s,len = 0,S1.length

[0,1].repeated_permutation(len) do |a|
  tmp_h = {:v => 0, :w => 0}
  S1.zip(a).each do |test|
    i,bit = test.first,test.last
    if bit==1
      tmp_h[:v] += i.first
      tmp_h[:w] += i.last
    end
  end
  tmp_a << tmp_h if tmp_h[:w] <= W
  s += 1
end

tmp_a = tmp_a.sort_by{|m| -m[:v]}
tmp_b = []
ans_v = 0

S2 = item[N/2...N]
s,len = 0,S2.length
[0,1].repeated_permutation(len) do |a|
  tmp_h = {:v => 0, :w => 0}

  S2.zip(a).each do |test|
    i,bit = test.first,test.last
    if bit==1
      tmp_h[:v] += i.first
      tmp_h[:w] += i.last
    end
  end

  if tmp_h[:w] <= W    
    x = tmp_a.detect{|e| tmp_h[:w] + e[:w] <= W }
    ans_v = [ans_v, x[:v] + tmp_h[:v]].max unless x.nil?
  end
  s += 1
end

puts ans_v