#include #define VARNAME(x) #x #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using ld = long double; template ostream& operator<<(ostream& os, const vector& v) { os << "sz:" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = (ll)1e9 + 7LL; constexpr ld PI = static_cast(3.1415926535898); template constexpr T INF = numeric_limits::max() / 10; constexpr ll W_MAX = 30000000; constexpr ll NW_MAX = 80000000; constexpr ll N_MAX = 1000; constexpr ll NVV_MAX = 30000000; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; ll W; cin >> N >> W; using P = pair; vector

p; ll wsum = 0; ll vsum = 0; for (int i = 0; i < N; i++) { ll w, v; cin >> v >> w; if (w <= W) { wsum += w; vsum += v; p.push_back(make_pair(v, w)); } } if (wsum <= W) { cout << vsum << endl; return 0; } if (N == 0) { cout << 0 << endl; return 0; } auto comp = [](const P& p1, const P& p2) { return __int128_t(p1.first) * __int128_t(p2.second) > __int128_t(p1.second) * __int128_t(p2.first); }; sort(p.begin(), p.end(), comp); N = p.size(); if (W * N < NW_MAX and W < W_MAX) { vector dp(W + 1, 0); dp[0] = 0; for (int i = 0; i < N; i++) { vector tmp(W + 1, 0); for (int j = 0; j <= W; j++) { tmp[j] = max(tmp[j], dp[j]); if (j + p[i].second <= W) { tmp[j + p[i].second] = max(tmp[j + p[i].second], dp[j] + p[i].first); } } dp = tmp; } cout << *max_element(dp.begin(), dp.end()) << endl; } else { ll cap = W; ll ans = 0; ll rest = N; ll used = 0; vector

res; for (used = 0; used < N and rest > N_MAX and rest * cap > NW_MAX; used++) { if (cap >= p[used].second) { rest--; cap -= p[used].second; ans += p[used].first; } else { res.push_back(p[used]); } } for (int i = used; i < N; i++) { res.push_back(p[i]); } p.clear(); p.shrink_to_fit(); if (rest * cap <= NW_MAX) { vector dp(cap + 1, 0); dp[0] = 0; for (int i = 0; i < rest; i++) { vector tmp(cap + 1, 0); for (int j = 0; j <= cap; j++) { tmp[j] = max(tmp[j], dp[j]); if (j + res[i].second <= W) { tmp[j + res[i].second] = max(tmp[j + res[i].second], dp[j] + res[i].first); } } dp = tmp; } cout << ans + *max_element(dp.begin(), dp.end()) << endl; return 0; } if (rest <= N_MAX) { ll VMAX = 0; for (const auto& e : res) { VMAX = max(VMAX, e.first); } const ll V_SMALL = (ll)sqrt(NVV_MAX / rest); const ll K = VMAX / V_SMALL; auto rescop = res; for (auto& e : rescop) { e.first = e.first / K; } ll vsum = 0; for (const auto& e : rescop) { vsum += e.first; } vector> dp(rest + 1, vector(vsum + 1, INF)); dp[0][0] = 0; for (int i = 0; i < rest; i++) { for (ll j = 0; j <= vsum; j++) { if (dp[i][j] != INF) { dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]); dp[i + 1][j + rescop[i].first] = min(dp[i + 1][j + rescop[i].first], dp[i][j] + rescop[i].second); } } } ll maxind = vsum; for (ll i = vsum; i >= 0; i--) { if (dp[rest][i] <= cap) { maxind = i; break; } } ll pos = maxind; for (int i = rest; i >= 1; i--) { if (dp[i][pos] != dp[i - 1][pos]) { ans += res[i - 1].first; pos -= rescop[i - 1].first; } } cout << ans << endl; return 0; } assert(false); cout << ans << endl; } return 0; }