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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <list>


using namespace std;

struct Item{
    long long a;
    long long b;
    long long ab;

    void print(){
        printf("i(a=%lld, b=%lld, ab=%lld)\n", a, b, ab);
    }
};

bool compare_a(const Item& first, const Item& second)
{
    return first.a > second.a;
}

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

    long long results[n];
    list<Item> items;
    for (int i = 0; i < n; i++){
        Item item;
        scanf(" %lld %lld", &(item.a), &(item.b));
        items.push_back(item);
    }

    //  sort by a desc                              nlogn
    items.sort(compare_a);

    //  create ab table ab = b + a*(n-1-k)     n
    //  results[n] = sum it all                     n
    long long position = n-1;
    results[n-1] = 0;
    for (list<Item>::iterator it=items.begin(); it != items.end(); ++it) {
        (*it).ab = (*it).b + (*it).a * position;
        position--;

        results[n-1] += (*it).ab;
    }

    //  find min i: ab + a_next_sum
    for (int k = n-2; k>=0; k--){
        //  find min opt_ix, opt_delta
        long long opt_ix = 0;
        long long opt_delta = items.front().ab;
        {
            long long a_sum = 0;
            long long ix = 0;
            for (list<Item>::iterator it=items.begin(); it != items.end(); ++it) {
                long long current_delta = (*it).ab + a_sum;
                if (opt_delta > current_delta) {
                    opt_delta = current_delta;
                    opt_ix = ix;
                }
                a_sum += (*it).a;
                ix++;
            }
        }

        //  results[k] = results[k+1] - min i
        results[k] = results[k+1] - opt_delta;

        //  j<opt_ix: update ab -= a, update
        //  remove opt_ix
        {
            long long ix = 0;
            for (list<Item>::iterator it=items.begin(); it != items.end(); ++it) {
                if (ix == opt_ix){
                    items.erase(it);
                    break;
                } else {
                    (*it).ab -= (*it).a;
                };

                ix++;
            }
        }
    }

    //  print results
    for(int i = 0; i < n; i++){
        printf("%lld\n", results[i]);
    }

    return 0;
}