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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// void qsort(void *base, size_t nmemb, size_t size,
//            int (*compar)(const void *, const void *));

// void *memcpy(void *dest, const void *src, size_t n);
// void *memmove(void *dest, const void *src, size_t n);

//-----
char C[7 + 2 + 1000000 * (7 + 1 + 13 + 2)];
int Cofs, Cend;

void fill(void) {
  Cofs = Cend = 0;
  for (;;) {
    int t = read(0, &C[Cend], sizeof(C) - Cend);
    if (t == 0) break;
    if (t < 0) continue;
    Cend += t;
  }
}

long long getint(void) {
  long long v = 0;
  while ((C[Cofs] < '0') || (C[Cofs] > '9')) ++Cofs;
  for (; (C[Cofs] >= '0') && (C[Cofs] <= '9'); ++Cofs) v = v * 10 + C[Cofs] - '0';
  return v;
}
//-----

typedef struct {
  int a;
  long long b;
  char v;
//int prv;
//int nxt;
} ab;

int cmp(const void * a, const void * b) {
  const ab * p = (const ab *)a;
  const ab * q = (const ab *)b;
  if (p->a < q->a) return +1;
  if (p->a > q->a) return -1;
  if (p->b < q->b) return +1;
  if (p->b > q->b) return -1;
  return 0;
};

void solve(int n) {
  ab AB[n];
  long long s = 0;
  int i, j, k;

  int new_a[n +5]; //+5 is fudge

  for (i = 0; i < n; ++i) {
    //scanf("%d%lld", &AB[i].a, &AB[i].b);
    AB[i].a = getint();
    AB[i].b = getint();
    AB[i].v = 1;
  }

  qsort(AB, n, sizeof(AB[0]), cmp);

/*
  for (i = 0; i < n; ++i) {
    AB[i].prv = i - 1;
    AB[i].nxt = i + 1;
  }
  AB[0].prv = -1;
  AB[n - 1].nxt = -1;
*/

  for (i = 0; i < n; ++i) {
    long long best = -1;
    int idx = 0;
    k = i;
    long long suma = 0;
    for (j = 0; j < n; ++j) if (AB[j].v) {
      int find = AB[j].a;
      long long res = AB[j].b + i * 1LL * AB[j].a;
      while ((k > 0) && (new_a[k - 1] > find)) {
        --k;
        suma += new_a[k];
      }

      if (k < i) res += suma - AB[j].a * 1LL * (i - k);
      if (res > best) {
        best = res;
        idx = j;
      }
    }
    s += best;
    AB[idx].v = 0;

    j = i;
    while ((j > 0) && (new_a[j - 1] > AB[idx].a)) --j;
    // dst, src, cnt
    memmove(&new_a[j + 1], &new_a[j], (i - j +1) * sizeof(new_a[0])); // +1 is fudge
    new_a[j] = AB[idx].a;

    printf("%lld\n", s);
  }
}

int main (void) {
  int n;
  fill();
  n = getint(); // scanf("%d", &n);
  // 1 <= n <= 1000000
  solve(n);
  return 0;
}