1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pll=pair<ll, ll>;
#define st first
#define nd second
const int N=5005;
pll line[N];
ll dp[N][N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) scanf("%lld%lld", &line[i].st, &line[i].nd);
    sort(line+1, line+n+1);
    for(int j=1; j<=n; ++j) dp[0][j]=max(dp[0][j-1], line[j].nd);
    for(int i=1; i<n; ++i) for(int j=1; j<=n; ++j) dp[i][j]=max(dp[i][j-1], dp[i-1][j-1]+line[j].st*i+line[j].nd);
    for(int i=0; i<n; ++i) printf("%lld\n", dp[i][n]);
}