// includes {{{ #include #include #include #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // #include // }}} using namespace std; using ll = long long; // こうですか.そうですよね // 0 <= z <= 1 を緩和するんですもんね // EPSの変化やDFSの探索順序,DFSをBFSに変えたらどうなるかなども気になるところです // EPSいらないね // doubleいるね,そうだよね // それ以降で取れるやつがあるかもしれないからね int n, W; constexpr int N = 5000; vector> objs; ll weight_sum[N]; ll value_sum[N]; ll global_best; void dfs(int i, ll val, ll weight_rest) { global_best = max(global_best, val); if(i == n) return; if(weight_rest == 0) return; int ok = i - 1, ng = n; while(ng - ok > 1) { int mid = (ng + ok) >> 1; ll sum = weight_sum[mid]; if(i - 1 >= 0) sum -= weight_sum[i - 1]; if(sum <= weight_rest) ok = mid; else ng = mid; } ll sum = 0; if(ok >= 0) sum += weight_sum[ok]; if(i - 1 >= 0) sum -= weight_sum[i - 1]; ll vsum = 0; if(ok >= 0) vsum += value_sum[ok]; if(i - 1 >= 0) vsum -= value_sum[i - 1]; global_best = max(global_best, val + vsum); // 実行可能 double now_upper_bound = val + vsum; if(ok + 1 < n) now_upper_bound += (double) objs[ok + 1].first / objs[ok + 1].second * weight_rest; if(floor(now_upper_bound) <= global_best) return; // drop or adopt if(weight_rest >= objs[i].second) dfs(i + 1, val + objs[i].first, weight_rest - objs[i].second); dfs(i + 1, val, weight_rest); } int main() { ios::sync_with_stdio(false), cin.tie(0); cin >> n >> W; for(int i = 0; i < n; i++) { ll v, w; cin >> v >> w; if(w <= W) objs.emplace_back(v, w); } n = objs.size(); sort(begin(objs), end(objs), [&](const pair &a, const pair &b) { return (double) a.first / a.second > (double) b.first / b.second; }); value_sum[0] = objs[0].first; for(int i = 1; i < n; i++) value_sum[i] = value_sum[i-1] + objs[i].first; weight_sum[0] = objs[0].second; for(int i = 1; i < n; i++) weight_sum[i] = weight_sum[i-1] + objs[i].second; dfs(0, 0, W); cout << global_best << endl; return 0; }