1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_N = 1000007;

pair <long long int, long long int> field[MAX_N];
long long int tab[2][MAX_N];
int n;

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%lld %lld", &field[i].first, &field[i].second);
    }

    sort(field + 1, field + n + 1);

    for (int i = 1; i <= n; ++i) {
        long long int prevMax = 0, currentMax = 0;
        prevMax = max(prevMax, tab[(i + 1) % 2][i - 1]);
        for (int j = i; j <= n; ++j) {
            tab[i % 2][j] = (i - 1) * field[j].first + field[j].second + prevMax;
            currentMax = max(currentMax, tab[i % 2][j]);
            prevMax = max(prevMax, tab[(i + 1) % 2][j]);
        }
        printf("%lld\n", currentMax);
    }

    return 0;
}