dttui1.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ii pair<int,int>
#define w first
#define v second

void brute(vector<ii> &a, vector<ii> &s, int n, int i, int w, int v) {
    for (int j = 0; j <= 1; j++) {
        if (j) {
            w += a[i].w;
            v += a[i].v;
        }
        if (i < n - 1) brute(a, s, n, i + 1, w, v);
        else s.push_back(ii(w, v));
        if (j) {
            w -= a[i].w;
            v -= a[i].v;
        }
    }
}

signed main() {
    int n, m; cin >> n >> m;
    int na = (n + 1) / 2, nb = n / 2;
    vector<ii> a(na), b(nb);
    for (int i = 0; i < na; i++) {
        cin >> a[i].w >> a[i].v;
    }
    for (int i = 0; i < nb; i++) {
        cin >> b[i].w >> b[i].v;
    }
    vector<ii> sa, sb;
    brute(a, sa, na, 0, 0, 0);
    brute(b, sb, nb, 0, 0, 0);
    sort(sa.begin(), sa.end());
    sort(sb.begin(), sb.end());
    vector<int> mb(sb.size());
    for (int i = 0; i < (int) sb.size(); i++) {
        if (i == 0) mb[i] = sb[i].v;
        else mb[i] = max(mb[i - 1], sb[i].v);
    }
    int ans = 0;
    for (int i = 0; i < (int) sa.size(); i++) {
        if (sa[i].w > m) continue;
        int l = 0, r = sb.size() - 1, t = -1;
        while (l <= r) {
            int md = (l + r) / 2;
            if (sb[md].w <= m - sa[i].w) {
                l = md + 1;
                t = md;
            } else r = md - 1;
        }
        if (t == -1) continue;
        else ans = max(ans, sa[i].v + mb[t]);
    }
    cout << ans << '\n';
}