#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define maxn 410
#define maxm 40010
using namespace std;
int quen[maxm],quev[maxm];
int head,tail;

int a[maxn],h[maxn];
int c[maxn],r[maxn];

int dp[maxm];
int n,u,m;
int i,j,d;
int cmp(int i,int j){
    return a[i]<a[j];
}

void insert(int x,int y){
     while (head<=tail&&quev[tail]<y) tail--;
     quen[++tail]=x;quev[tail]=y;
}
int main(){
    while (scanf("%d",&n)==1){
          if (n==0) {printf("0\n");continue;}
          for (i=1;i<=n;i++)
              scanf("%d%d%d",&h[i],&a[i],&c[i]);
          for (i=1;i<=n;i++) r[i]=i;
          sort(r+1,r+n+1,cmp);
          memset(dp,0,sizeof(dp));
          m=a[r[n]];
          for (i=1;i<=n;i++){
              u=r[i];
              for (d=0;d<h[u];d++){
                  head=1;tail=0;
                  for (j=0;j<=(a[u]-d)/h[u];j++){
                      insert(j,dp[j*h[u]+d]-j*h[u]);
                      while (head<=tail&&quen[head]<j-c[u]) head++;
                      //while (head<=tail&&quev[head]+j*h[u]>a[u]) head++;
                      dp[j*h[u]+d]=j*h[u]+quev[head];
                  }
              }
              //for (j=1;j<=m/2;j++) if (dp[j]!=0)
              //    printf("%d %d\n",j,dp[j]);
              //system("pause");
          }
          printf("%d\n",dp[m]);
    }
    return 0;
}