program budget;
  var
    a:array[1..60,0..3] of integer;
b:array[1..60,0..2] of integer;
    f:array[0..60,0..3200] of integer;
    n,m,i,s,v,p,q,j,w:integer;
  begin
    fillchar(a,sizeof(a),0);
    fillchar(b,sizeof(b),0);
    assign(input,'budgetb.in');
    assign(output,'budgetb.out');
    reset(input);
    rewrite(output);
    readln(n,m,w);
    n:=n div 10;
    s:=0;
    for i:=1 to m do
      begin
        readln(v,p,q);
        v:=v div 10;
        if q=0 then begin
                   inc(s);
                   a[s,0]:=v;
                   a[s,3]:=i;
                   b[s,0]:=p;
                 end
             else begin
                   for j:=1 to s do
                     if a[j,3]=q then break;
                   if a[j,1]=0 then begin a[j,1]:=v;b[j,1]:=p; end
                            else begin a[j,2]:=v;b[j,2]:=p; end;
                 end;
      end;
    fillchar(f,sizeof(f),0);
    m:=s;
    for i:=1 to m do
      for j:=0 to n do
        begin
          f[i,j]:=f[i-1,j];
          if (j>=a[i,0]) and (f[i,j]<f[i-1,j-a[i,0]]+a[i,0]*b[i,0])
then f[i,j]:=f[i-1,j-a[i,0]]+a[i,0]*b[i,0];
           if (j>=(a[i,0]+a[i,1])) and (f[i,j]<f[i-1,j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]) then f[i,j]:=f[i-1,j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1];
           if (j>=(a[i,0]+a[i,2])) and (f[i,j]<f[i-1,j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]) then f[i,j]:=f[i-1,j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2];
if (j>=(a[i,0]+a[i,1]+a[i,2])) and (f[i,j]<f[i-1,j-a[i,0]-a[i,1]-a[i,2]]+a[i,0]*b[i,0]+
a[i,1]*b[i,1]+a[i,2]*b[i,2]) then
 f[i,j]:=f[i-1,j-a[i,0]-a[i,1]-a[i,2]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]+a[i,2]*b[i,2];
        end;
    writeln(f[m,n]*10);
    close(input);
    close(output);
  end.