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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define scanf(...) scanf(__VA_ARGS__)?:0
#define e1 first
#define e2 second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
int n,dodany[1000001],tp[1000001];
ll st[1000001];
pil s[1000001];
ll skoszt=0;
void wrzuc_pot(int a)
{
	while (a<=n) tp[a]++,a+=a&-a;
}
int suma_pot(int a)
{
	int ret=0;
	while (a) ret+=tp[a],a-=a&-a;
	return ret;
}
void wrzuc_prz(int a,ll x)
{
	while (a<=n) st[a]+=x,a+=a&-a;
}
ll suma_prz(int a)
{
	ll ret=0;
	while (a) ret+=st[a],a-=a&-a;
	return ret;
}
void wrzuc(int a)
{
	dodany[a]=1;
	wrzuc_pot(a);
	wrzuc_prz(a,s[a].e1);
}
ll kosztd(int a)
{
	ll ret=s[a].e2;
	ret+=(ll)suma_pot(a-1)*s[a].e1;
	ret+=suma_prz(n)-suma_prz(a);
	//FOR(i,1,a-1) if (dodany[i]) ret+=s[a].e1;
	//FOR(i,a+1,n) if (dodany[i]) ret+=s[i].e1;
	return ret;
}
int main()
{
	scanf("%d",&n);
	FOR(i,1,n) scanf("%d%lld",&s[i].e1,&s[i].e2);
	sort(s+1,s+n+1);
	FOR(i,1,n)
	{
		ll mkoszt=0; int w=0;
		FORD(j,n,1) if (!dodany[j])
		{
			ll pom=kosztd(j);
			if (pom>mkoszt) mkoszt=pom,w=j;
		}
		wrzuc(w);
		skoszt+=mkoszt;
		printf("%lld\n",skoszt);
	}
}