1 #include <cstdio> 2 #include <cstring> 3  4 int map[15][15]; 5 int dp[10005]; 6 int n, C; 7  8 int max(int a, int b) { 9     return a>b ? a:b;10 }11 12 void ZeroOnePack(int v, int c) {13     for (int i=C; i>=c; --i)14         dp[i] = max(dp[i-c]+v, dp[i]);15 }16 17 void CompeletePack(int v, int c) {18     for (int i=c; i<=C; ++i)19         dp[i] = max(dp[i-c]+v, dp[i]);20 }21 22 void MultiPack(int v, int c, int k) {23     if (c*k >= C) {24         CompeletePack(v, c);25         return ;26     }27     int r = 1;28     while (r < k) {29         ZeroOnePack(r*v, r*c);30         k = k - r;31         r <<= 1;32     }33     ZeroOnePack(k*v, k*c);34 }35 36 int main() {37     int v, c;38     char s[15];39     int i, j;40 41     while (scanf("%d %d", &n, &C) != EOF) {42         memset(map, 0, sizeof(map));43         memset(dp, 0, sizeof(dp));44         for (i=0; i<n; ++i) {45             scanf("%s %d %d", s, &v, &c);46             map[v][c]++;47         }48         for (i=1; i<=10; ++i) {49             for (j=0; j<=10; ++j) {50                 if (map[i][j])51                     MultiPack(i, j, map[i][j]);52             }53         }54         printf("%d\n", dp[C]);55     }56 57     return 0;58 }