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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include<cstdio>
#include <list>
using namespace std;

class Polana{
	
private:
	int a;
	long long int b;
	
public:
	Polana();
	Polana(int a, long long int b);
	~Polana();
	
	int getA();
	long long int getB();
	long long int countMushrooms(int days);
};

Polana::Polana(){};

Polana::Polana(int a, long long int b){
	this->a = a;
	this->b = b;
};
Polana::~Polana(){};

int Polana::getA(){ return this->a;};
long long int Polana::getB(){ return this->b;};


long long int Polana::countMushrooms(int days){ 
	return (b + a*days);
};

bool compare_Polana_a(Polana first, Polana second){
	if (first.getA() < second.getA())
		return true;
	return false;
};

bool compare_Polana_b(Polana first, Polana second){
	if (first.getB() > second.getB())
		return true;
	return false;
};

int count_mushrooms_for_array(Polana* tab, int size){

	long long int sum = 0;
	for (int i=0; i<size; i++){
		sum += tab[i].countMushrooms(i);
	}
	return sum;
}

int count_mushrooms(list<Polana> polany){
	
	int j = 0;
	long long int sum = 0;
	for(list<Polana>::iterator it=polany.begin(); it != polany.end(); ++it){
		sum += (*it).getA()*j + (*it).getB();
		j = j + 1;
	}
	return sum;
}

void babelek(Polana * tab, Polana p, int j, int k){ // k - liczba dni
	for (; j<k; j++){
		if (p.countMushrooms(j) > tab[j].countMushrooms(j)){
			Polana temp = tab[j];
			tab[j] = p;
			babelek(tab, temp, j, k);
		}
	}
}

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

  list<Polana> polany;
  
  int a;
  long long int b;
  long long int max_b = -1;
  for(int i = 0; i < n; i++){
     scanf("%d %d", &a, &b);
	 if (b > max_b){
		 max_b = b;
	 }
	 polany.push_back(Polana(a, b));
  }
  
  cout << max_b << endl;
  
  if (n > 1){
  
	  int j = 0;	  
	  polany.sort(compare_Polana_a);

	  Polana * sorted_a = new Polana [n];
	  for(list<Polana>::iterator it=polany.begin(); it != polany.end(); ++it){
		sorted_a[j] = *it;
		j = j + 1;
	  } 
	  
		Polana * temp = new Polana [n]; 
	  for(int k=2; k < n; k++){
		for (int i = 0; i < k; i++){
			temp[i] = sorted_a[n - k + i];
		}
		
		for (int i = 0; i < (n-k); i++){
			Polana p = sorted_a[i];
			/*
			for (int j=0; j<k; j++){
				if (p.countMushrooms(j) > temp[j].countMushrooms(j)){
					temp[j] = p;
					break;
				}
			}
			*/
			babelek(temp, p, 0, k);
		}
		
		long long int sum = 0;
		for(int i=0; i<k; i++){
			sum += temp[i].countMushrooms(i);
		}
	    cout << sum << endl;
	  }
		delete[] temp;
	  
	  // przypadek ostatni, k = n;
	  cout << count_mushrooms_for_array(sorted_a, n) << endl;
	  
	  delete[] sorted_a;
  }
  
  return 0;
}