#include #include #include constexpr long long inf = std::numeric_limits::max() / 2; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector c(n + 1); std::vector v(n + 1); for (int w = 1; w <= n; ++w) { std::cin >> c[w] >> v[w]; c[w] = std::min(c[w], n / w); } std::vector dp(n + 1, std::vector(n + 1, -inf)); std::fill(std::begin(dp[0]), std::end(dp[0]), 0); for (int w = n; w >= 1; --w) { for (int pw = 1; c[w] > 0; pw <<= 1) { const int k = std::min(pw, c[w]); c[w] -= k; const int dw = k * w; const long long dv = k * v[w]; for (int num = n / w; num >= k; --num) { for (int wsum = n; wsum >= dw; --wsum) { dp[num][wsum] = std::max(dp[num][wsum], dp[num - k][wsum - dw] + dv); } } } } for (int num = 1; num <= n; ++num) { std::cout << dp[num][n] << '\n'; } return 0; }