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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

#include <unistd.h>

using namespace std;

const int kMaxSize = 1 << 25;

char c_[kMaxSize];

class CustomIo {
 public:
  CustomIo() : pos_in_(0), pos_out_(0) {
    read(0, c_, sizeof(c_));
  }

  ~CustomIo() {
    write(1, c_, pos_out_);
  }

  long long Read() {
    long long ret = 0;
    while (!IsDigit(c_[pos_in_])) ++pos_in_;
    do {
      ret *= 10;
      ret += c_[pos_in_];
      ret -= '0';
    } while (IsDigit(c_[++pos_in_]));
    return ret;
  }

  void Write(const long long a) {
    if (a >= 10) Write(a / 10);
    c_[pos_out_++] = (a % 10) + '0';
  }

  void Writeln(const long long a) {
    Write(a);
    c_[pos_out_++] = '\n';
  }

 private:
  static bool IsDigit(const char c) {
    return (c >= '0') && (c <= '9');
  }

  int pos_in_;
  int pos_out_;
};

int main() {
  CustomIo cio;
  const int n = cio.Read();
  vector<pair<long long, long long> > ab(n);
  for (int i = 0; i < n; ++i) {
    ab[i].first = cio.Read();
    ab[i].second = cio.Read();
  }
  sort(ab.begin(), ab.end());

  vector<long long> ret;

  long long result = 0;
  for (int i = 0; i < ab.size(); ++i) result += i * ab[i].first + ab[i].second;

  while (!ab.empty()) {
    // cerr << result << endl;
    ret.push_back(result);

    long long suffix = 0;
    int best_pos = ab.size() - 1;
    long long best_loss = best_pos * ab[best_pos].first + ab[best_pos].second + suffix;

    for (int i = ab.size() - 1; i >= 0; --i) {
      const long long loss = i * ab[i].first + ab[i].second + suffix;
      suffix += ab[i].first;
      // cerr << "loss at " << i << " is " << loss << endl;
      if (loss < best_loss) {
        best_pos = i;
        best_loss = loss;
      }
    }
    // cerr << best_pos << endl;
    ab.erase(ab.begin() + best_pos);
    result -= best_loss;
  }

  reverse(ret.begin(), ret.end());
  for (int i = 0; i < n; ++i) cio.Writeln(ret[i]);
}