黒歴史61

#include

using namespace std;
typedef pair P;
int n,k,dp[2003][2003],ans;
P d[2003];
int nau[2003][11],pre[2003][11];

int main(){
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;i++){
scanf("%d%d",&d[i].first,&d[i].second);
}
d[0].first = 100000000;
sort(d,d + n+1,greater

());
d[0].first = 0;
for(int i = 1;i <= k;i++){
for(int j = 1;j <= n;j++){
// dp[i][j] = dp[i][j-1];
int hi = dp[i-1][j-1] + d[j].first + pre[j-1][d[i].second]*2;
if(dp[i][j] < hi){
nau[j][d[i].second]++;
dp[i][j] = hi;
}
ans = max(ans,dp[i][j]);

}
for(int j = 1;j <= n;j++){
for(int c = 1;c <= 10;c++){
pre[j][c] += nau[j][c];
nau[j][c] = 0;
}
}
}
printf("%d\n",ans);

for(int i = 1;i <= k;i++){
for(int j = 1;j <= n;j++){
printf("%d ",dp[i][j]);
}
printf("\n");
}

return 0;
}