#include <iostream>
#include <vector>
#include <deque>
#include <map>
#include <unordered_map> // Using unordered_map for potentially faster average performance
#include <algorithm>

using namespace std;

// Use long long for values and intermediate calculations that might exceed 32-bit integer limits.
using ll = long long; 

// Define a large negative number to represent -infinity. 
// Using a value far from LLONG_MIN to avoid potential overflow issues during calculations.
// A value around -3e18 should be safe given constraints N <= 2500 and |v_i| <= 10^9.
// Max possible total value can be around N * 10^9 approx 2.5e12. Min possible -2.5e12.
const ll INF = -3e18; 

int main() {
    // Faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Number of item types and maximum total weight/items constraint
    cin >> N;

    // Store item properties: c[i] = count of items of type i, v[i] = value of item type i
    vector<int> c(N + 1);
    vector<ll> v(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> c[i] >> v[i];
        // The weight of item type i is implicitly i.
    }

    // DP table: dp[k][w] stores the maximum value achievable using exactly k items with total weight exactly w.
    // Initialize all states to -infinity, except the base case.
    vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, INF));
    dp[0][0] = 0; // Base case: 0 items, 0 weight, 0 value.

    // Iterate through each item type i from 1 to N
    for (int i = 1; i <= N; ++i) {
        // Create a new DP table dp_new based on the state after processing items 1 to i-1 (which is current dp table).
        // Updates related to item type 'i' will be stored in dp_new.
        // Initializing dp_new as a copy ensures that states not updated by item 'i' retain their previous values.
        vector<vector<ll>> dp_new = dp; 

        // The monotonic queue optimization works on diagonals in the (k, w) state space.
        // A diagonal is defined by a constant value D = w - k*i.
        // We group states from the previous DP table `dp` based on their diagonal D.
        // unordered_map is used for potentially faster average lookup times compared to map.
        // It maps diagonal D to another map, which stores {k -> dp[k][w]} for states on that diagonal.
        unordered_map<ll, map<int, ll>> states_on_diagonal; 
        for(int k = 0; k <= N; ++k) {
            for(int w = 0; w <= N; ++w) {
                // Check if the state (k, w) is reachable (value > -infinity). Use INF/2 check to avoid arithmetic issues near INF.
                if (dp[k][w] > INF / 2) { 
                    // Calculate the diagonal identifier D for state (k, w).
                    ll D = (ll)w - (ll)k * i;
                    // Store the value dp[k][w] associated with state k on diagonal D.
                    states_on_diagonal[D][k] = dp[k][w];
                }
            }
        }

        // Process each diagonal D found in the previous states.
        for (auto const& [D, k_map] : states_on_diagonal) {
             // Initialize a deque for the monotonic queue optimization.
             // Stores pairs { Y_k', k' }, where Y_k' = dp[k'][k'*i+D] - k'*v[i].
             // The queue maintains elements in decreasing order of Y_k', enabling efficient max query.
             deque<pair<ll, int>> dq; 
             
             // Determine the valid range of k values [k_start, k_end] for this diagonal D.
             // A state (k, w) is valid if 0 <= k <= N and 0 <= w <= N.
             // Substituting w = k*i + D, we need 0 <= k*i + D <= N.
             
             // Calculate minimum k (k_start).
             int k_start = 0;
             if (D < 0) {
                 // Need k*i + D >= 0 => k*i >= -D. Since i >= 1, k >= -D/i.
                 // We need the smallest integer k satisfying this, which is ceil(-D / i).
                 // Integer division computes ceil(a/b) for positive a,b as (a + b - 1) / b.
                 if (i > 0) { // Guarantee i >= 1 from problem statement.
                    k_start = (int)((-D + i - 1) / i);
                 }
             }
             k_start = max(0, k_start); // Ensure k is non-negative.

             // Calculate maximum k (k_end).
             int k_end;
             ll num = (ll)N - D; // Need k*i + D <= N => k*i <= N - D
             if (num < 0) {
                 // If N - D < 0, then k*i <= num < 0. Since k >= 0 and i >= 1, k*i >= 0.
                 // There is no non-negative k satisfying this condition.
                 k_end = -1; 
             } else {
                 // If N - D >= 0, then k <= (N - D) / i. We need the largest integer k.
                 // Standard integer division performs floor operation for non-negative numerator.
                 if (i > 0) { // Guaranteed i >= 1
                     k_end = (int)(num / i); 
                 } else { // Defensive coding, should not happen.
                     k_end = N; // If i were 0, k*0 <= num is always true for num >= 0. k restricted by N.
                 }
                 k_end = min(N, k_end); // k also cannot exceed N.
             }
             
             // Iterate through k in the valid range [k_start, k_end] for this diagonal.
             for (int k = k_start; k <= k_end; ++k) {
                 // Calculate the corresponding weight w for the current k on this diagonal.
                 ll current_w = (ll)k * i + D;
                 // Check bounds for w, although the k range calculation should make this redundant.
                 // if (current_w < 0 || current_w > N) continue; 

                 // Monotonic Queue maintenance: Remove elements from the front that are outside the window.
                 // The window for state k includes previous states k' such that k - c[i] <= k' <= k.
                 // We need the values corresponding to k' >= k - c[i].
                 while (!dq.empty() && dq.front().second < k - c[i]) {
                     dq.pop_front();
                 }

                 // Check if the state (k, current_w) was reachable in the DP table `dp` (before processing item i).
                 // Access this value using the precomputed `k_map` for the current diagonal D.
                 ll val_old = INF;
                 auto it = k_map.find(k);
                 if (it != k_map.end()) {
                    val_old = it->second; // Get the stored dp[k][w] value.
                 }

                 // If this state (k, current_w) was reachable...
                 if (val_old > INF / 2) { 
                    // Calculate the value Y_k = dp[k][current_w] - k * v[i] used for queue optimization.
                    ll Y_k = val_old - (ll)k * v[i];
                    // Maintain the monotonic property of the queue (decreasing Y values).
                    // Remove elements from the back with Y value less than or equal to the current Y_k.
                    while (!dq.empty() && dq.back().first <= Y_k) {
                        dq.pop_back();
                    }
                    // Add the current state's information {Y_k, k} to the back of the queue.
                    dq.push_back({Y_k, k});
                 }

                 // If the queue is not empty, there is a potential maximum value within the window.
                 if (!dq.empty()) {
                     // The maximum Y_k' value within the window [k-c[i], k] is at the front of the deque.
                     ll max_Y_k_prime = dq.front().first;
                     // Calculate the potential new maximum value for state (k, current_w) using item i optimally.
                     // This is derived from the formula: dp_new[k][w] = max { Y_k' } + k*v[i].
                     ll value_with_item_i = max_Y_k_prime + (ll)k * v[i];
                     
                     // Update the state (k, current_w) in the `dp_new` table.
                     // Take the maximum of its current value (which might be from `dp` or an earlier update)
                     // and the newly calculated value `value_with_item_i`.
                     // Cast current_w back to int for indexing, assuming it remains within [0, N].
                     dp_new[k][(int)current_w] = max(dp_new[k][(int)current_w], value_with_item_i);
                 }
             }
        }
        // After processing all diagonals for item type i, update the main DP table `dp`
        // by moving the contents of `dp_new`. This is efficient using std::move.
        dp = std::move(dp_new); 
    }

    // After processing all item types, find the maximum value for each required number of items k.
    for (int k = 1; k <= N; ++k) {
        ll max_val = INF;
        // The maximum value for exactly k items can occur at any total weight w from 0 to N.
        for (int w = 0; w <= N; ++w) {
            max_val = max(max_val, dp[k][w]);
        }
        // Output the maximum value found for exactly k items.
        // The problem guarantees that a valid selection exists for each k, so max_val should not be INF.
        cout << max_val << "\n";
    }

    return 0;
}