3732 Ahui Writes Word
5245 ワード
// N C
// 0 1 N=100000 C=10000
// v,c 10
// 100
// dp
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MOD 1000000007
#define maxn 10010
int dp[maxn];
int mp[110][110]; // v,c
char str[110];
//int use[maxn*10];
int main(){
int i,j,k;
int n,c;
int u,v;
while(scanf("%d %d",&n,&c)!=EOF){
memset(mp,0,sizeof(mp));
for(i=0;i<n;i++){
scanf("%s %d %d",str,&u,&v);
// printf("%s ");
mp[u][v]++;
}
for(i=0;i<=c;i++) dp[i]=0;
int tp;
for(u=0;u<=10;u++)
for(v=0;v<=10;v++){
if(mp[u][v]){
k=1;
while(mp[u][v]>=k){
tp=k*v;
for(j=c;j>=tp;j--)
if(dp[j]<dp[j-tp]+k*u)
dp[j]=dp[j-tp]+k*u;
mp[u][v]-=k;
k=k<<1;
}
if(mp[u][v]){
k=mp[u][v];
tp=k*v;
for(j=c;j>=tp;j--)
if(dp[j]<dp[j-tp]+k*u)
dp[j]=dp[j-tp]+k*u;
}
}
}
printf("%d
",dp[c]);
}
return 0;
}