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
#include<cstdio>
#include<algorithm>
using namespace std;
#define FI first
#define SE second
#define LL long long
#define _P pair<long long, long long>

int n;

LL score, sum_picked;
bool picked[1001000];
_P tab[1001000];

bool cmp(_P a, _P b){
	if(a.FI == b.FI)
		return a.SE > b.SE;
	return a.FI < b.FI;
	}

LL add(){
	LL ret = 0;
	int which = 0;
	LL sum_to_end = sum_picked, sum_now, before = 0;
	
	for(int i = 0; i < n; ++i){
		if(picked[i]){
			sum_to_end -= tab[i].FI;
			++before;
			}
		else{
			sum_now = tab[i].SE + tab[i].FI*before + sum_to_end;
			//printf("   trying to add %d: %lld\n", i, sum_now);
			if(sum_now>ret){
				ret = sum_now;
				which = i;
				}
			}
		}
	picked[which] = true;
	sum_picked += tab[which].FI;
	//printf("now picked: %d(%lld %lld)\n", which, tab[which].FI, tab[which].SE);
	return ret;
	}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%lld %lld", &tab[i].FI, &tab[i].SE);
	sort(tab, tab+n, cmp);
	//for(int i = 0; i < n; ++i)
	//	printf("%lld %lld\n", tab[i].FI, tab[i].SE);
	for(int i = 0; i < n; ++i){
		score += add();
		printf("%lld\n", score);
		}
	}