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 <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

typedef long long LL;

const int MN = 1000005;

pair < LL, LL > T[MN];
LL pos[MN], res[MN];
int del[MN];


int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%lld%lld", &T[i].fi, &T[i].se);
	sort(T, T+n);
	LL suma = 0LL;
	for(int i = 0; i < n; ++i)
	{
		suma += ((((LL)(i))*T[i].fi) + T[i].se);
		pos[i] = (LL)i;
	}
	for(int i = 0; i < n; ++i)
	{
		res[i] = suma;
		LL currbest = 5000000000000000000LL;
		LL currSuma = 0LL;
		LL kozdra = 0LL;
		int currZly, x;
		x = 0;
		for(int j = n - 1; j >= 0; --j)
		{
			if(!del[j])
			{
				LL wsp = pos[j] * T[j].fi;
				if(currSuma + T[j].se + wsp < currbest)
				{
					currbest = currSuma + T[j].se + wsp;
					currZly = j;
				}
				currSuma += T[j].fi;
				//kozdra += currSuma;
			}
		}
		suma -= currbest;
		del[currZly] = 1;
		for(int i = currZly + 1; i < n; ++i)
			--pos[i];
	}
	for(int i = n - 1; i >= 0; --i)
		printf("%lld\n", res[i]);
}