// Aircraft Maintenance: Shortest Time
// Dynamic Programming
// By Seksun Suwanmanee, Dept. of Computer Engineering PSU Hatyai
// July 2010

#include <stdio.h>
#include <string.h>
#define MX 100     //maximum number of crews
#define MXHRS 300  //max hours per crew

// global variables
int ncrew,ntask,
    task[5*MX][2]={},    //Let's suppose there are at most 5*MX tasks
    crew[MX][3]={},
    Table[MXHRS][5*MX][MX]={}; //lookup table for reducing the recursive calls
int mxhrs;
char inp[3][MX],taskID[5* MX][MX];
int step=0, depth=0, mxDepth=0, maxSoFar=0; // just for stat and tracking

int string2int(char s[])
{ int i,r=0,len=strlen(s);
  for(i=0;i<len;i++) 
     r = 10*r + (s[i]-'0');
  return r;
}

int getMin(int x, int y)
{ 
    return (x<=y?x:y) ;
}

int getMax(int x, int y)
{ 
    return (x>=y?x:y) ;
}

//Dynamic recursive function
int ks(int mWHr, int wHr, int ti,int ci);

int main()
{
    int i,j, totalCost, minWHrs;
    
    //local test
    //freopen("smallinput.txt","r",stdin);
    //freopen("inputSample.txt","r",stdin);
    //freopen("inputTest.txt","r",stdin);
    //freopen("Dinput.txt","r",stdin);
    // Reading the input
    ncrew=0; ntask=0; mxhrs=0;
    while( scanf("%s %s %s",inp[0],inp[1],inp[2]) == 3 )
    {  // crew information begins with number
       if (inp[0][0]>='0' && inp[0][0]<='9') 
       {   i=string2int(inp[0]); // crew number
           crew[i][0]=string2int(inp[1]); // crew skill level
           crew[i][1]=string2int(inp[2]); // crew cost per hour
           crew[i][2]=0;  // initial working hours = 0 for all crew
           ncrew++;
        }               
       else // task information
       {  strcpy(taskID[ntask],inp[0]); //task ID
          task[ntask][0]=string2int(inp[1]); // task level
          task[ntask][1]=string2int(inp[2]); // task hours          
          mxhrs+=task[ntask][1];
          ntask++;                
       } 
    }
    
    //show input data
    for(i=0;i<ncrew;i++) 
      printf("%d %d %d\n",crew[i][0], crew[i][1],crew[i][2]);
    for(i=0;i<ntask;i++) 
      printf("%s %d %d\n",taskID[i], task[i][0],task[i][1]);
    printf("ntask = %d, ncrew = %d, mxhrs=%d\n",ntask,ncrew,mxhrs);
    
    
    //start from the last highest-level task and highest-level crew 
    minWHrs = ks(0,mxhrs,ntask-1,ncrew-1);
    printf("\nmin working hours = %d \n",minWHrs);

    printf("\nStat: step=%d maxSoFar=%d mxDepth=%d\n",step, maxSoFar,mxDepth );
    
    //getch();
    return 0;
}

//Dynamic recursive function
// mWHr = max working hours so far
// wHr = working hours of remaining tasks
// ti = current index of task, ci = current index of crew
int ks(int mWHr,int wHr, int ti,int ci)
{   int selectCi, doTiSelectCi, doTiSelectCi_1;

    depth++; if(mxDepth<depth) mxDepth=depth;
    step++; //if(step>2000000) {step--;return MXHRS+1; }
    
    if (mWHr>MXHRS) { depth--; return MXHRS+1; }
    if(wHr<=0 || ti<0  ) { depth--; return mWHr; }
    
    if (Table[mWHr][ti][ci]!=0) 
     { depth--; return Table[mWHr][ti][ci]; }

    //crew does not have enough skill
    if (crew[ci][0]<task[ti][0])
    { Table[mWHr][ti][ci]= MXHRS+1;
      depth--;
      return MXHRS+1;
    }
    
    // last crew is selected for the last task
    if (ci==0 && wHr==0) //IMPORTANT wHr==0 
    {  crew[ci][2]+=task[ti][1];  //add task hours
       if (crew[ci][2]> (mWHr) ) 
       { Table[mWHr][ti][ci]=crew[ci][2];  
         //printf("mWHr=%d new max=%d ti= %d ci=%d \n",mWHr,crew[ci][2],ti,ci);
        }
       else Table[mWHr][ti][ci]=mWHr;
       crew[ci][2]-=task[ti][1]; //remove task hours
       //printf("mWHr=%d max=%d ti= %d ci=%d \n",mWHr,Table[mWHr][ti][ci],ti,ci);
       if(maxSoFar<Table[mWHr][ti][ci]) maxSoFar=Table[mWHr][ti][ci];
       depth--;
       return Table[mWHr][ti][ci];       
    }
      
    // Select Crew ci for task ti and then do next task (ti-1) from ncrew-1
    crew[ci][2]+=task[ti][1];  //add task hours
    if (crew[ci][2]>(mWHr) ) selectCi=crew[ci][2]; 
    else selectCi=mWHr;
    doTiSelectCi=ks(selectCi,wHr-task[ti][1],ti-1,ncrew-1);
     
    // Not select crew ci for task ti but select ci-1 for task i 
    // and then do task i-1 from ncrew-1
    crew[ci][2]-=task[ti][1]; //remove task hours
    doTiSelectCi_1 = ks(ks(mWHr,wHr,ti,ci-1) ,wHr-task[ti][1] ,ti-1, ncrew-1);
    Table[mWHr][ti][ci]=getMin(doTiSelectCi,doTiSelectCi_1);
    
    if(maxSoFar<Table[mWHr][ti][ci]) maxSoFar=Table[mWHr][ti][ci];
    //printf("mWHr=%d new mx=%d ti= %d ci=%d \n",mWHr,Table[mWHr][ti][ci] ,ti,ci);
    depth--;
    return Table[mWHr][ti][ci];
}