/*多重背包问题。把a[i]排下序，然后把a[i]作为选第i件物品时的背包容量V。最后结果要[0, max(a[i])]遍历一遍，找到最大值。*/ //My Code: #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; const int N = 40007; const int M = 407; class node {
   public: int h, c, a;     friend bool operator < (const node& t1, const node& t2) {
   return t1.a < t2.a;     } }t[M]; int f[N]; int main() {
   //freopen("data.in", "r", stdin); int k, i, ans, j, m; int h1, V, c1; while(~scanf("%d", &k)) {
           memset(t, 0, sizeof(t));         h1 = V = c1 = 0; for(i = 0; i < k; i++) {
               scanf("%d%d%d", &t[i].h, &t[i].a, &t[i].c); if(t[i].h > h1)    h1 = t[i].h; if(t[i].a > V)    V = t[i].a; if(t[i].c > c1) c1 = t[i].c;         }         sort(t, t + k);         memset(f, 0, sizeof(f)); for(i = 0; i < k; i++) {
   if(t[i].c*t[i].h > t[i].a) {
   for(j = t[i].h; j <= t[i].a; j++) {
                       f[j] = max(f[j], f[j-t[i].h] + t[i].h);                 } continue;             }             m = 1; while(t[i].c) {
   if(m > t[i].c)    m = t[i].c;                 t[i].c -= m; for(j = t[i].a; j >= m*t[i].h; j--) {
                       f[j] = max(f[j], f[j-m*t[i].h] + m*t[i].h);                 }                 m <<= 1;             }         }         ans = 0; for(i = 0; i <= V; i++) {
               ans = ans < f[i] ? f[i] : ans;         }         cout << ans << endl;     } return 0; } //ps: 2011年最后一天， Happy New Year  ^_^