uses math;

var f:array[0..5000]of longint;
    c:array[0..60,0..1000,0..2]of longint;
    v,w:array[1..60]of longint;
    vf,vv:array[1..60]of boolean;
    i,j,k,n,m,s,q:longint;
    b:array[1..60,0..10]of longint;

procedure did(step,ans1,ans2:longint);
var ii:longint;
begin
 if step=j then
  begin
   inc(c[i,0,0]);
   c[i,c[i,0,0],1]:=ans1+v[i];
   c[i,c[i,0,0],2]:=ans2+w[i];
   exit;
  end;
 for ii:=1 to b[i,0]do
  if not(vv[b[i,ii]]) then
   begin
    vv[b[i,ii]]:=true;
    did(step+1,ans1+v[b[i,ii]],ans2+w[b[i,ii]]);
    vv[b[i,ii]]:=false;
   end;
end;

begin
 assign(input,'budgetb.in');reset(input);
 assign(output,'budgetb.out');rewrite(output);
 readln(n,m,s);n:=n div 10;
 for i:=1 to m do
  begin
   readln(v[i],w[i],q);v[i]:=v[i]div 10;
   w[i]:=w[i]*v[i];
   if q<>0 then
    begin inc(b[q,0]);b[q,b[q,0]]:=i;vf[i]:=true;end;
  end;
 for i:=1 to m do
  for j:=0 to b[i,0]do did(0,0,0);
 for j:=1 to m do
  if not(vf[j])then
   for k:=1 to c[j,0,0]do
    for i:=n downto c[j,k,1] do
     f[i]:=max(f[i],f[i-c[j,k,1]]+c[j,k,2]);
 writeln(f[n]*10);
 close(output);
end.