var f:array[0..3200] of longint;
a:array[1..60,0..2] of longint;
b:array[1..60,1..2] of longint;
ans,n,m,i,j,v,p,q,tt:longint;
begin
assign(input,'budgetb.in');
reset(input);
assign(output,'budgetb.out');
rewrite(output);
readln(n,m,tt);
n:=n div 10;
for i:=1 to m do
begin
readln(v,p,q);
v:=v div 10;
b[i,1]:=v;b[i,2]:=b[i,1]*p;
if q>0 then begin
if a[q,1]<>0 then a[q,2]:=i
else a[q,1]:=i; end
else a[i,0]:=1;
end;
for i:=1 to m do
if a[i,0]<>0 then
begin
for j:=n downto 0 do
   begin
   if j-b[i,1]>=0 then
if f[j]<f[j-b[i,1]]+b[i,2] then f[j]:=f[j-b[i,1]]+b[i,2];

   if (a[i,1]<>0) and (j-b[i,1]-b[a[i,1],1]>=0) then
       if f[j]<f[j-b[i,1]-b[a[i,1],1]]+b[i,2]+b[a[i,1],2] then
       f[j]:=f[j-b[i,1]-b[a[i,1],1]]+b[i,2]+b[a[i,1],2];

   if a[i,2]<>0 then
      begin
      if j-b[i,1]-b[a[i,2],1]>=0 then
       if f[j]<f[j-b[i,1]-b[a[i,2],1]]+b[i,2]+b[a[i,2],2] then
       f[j]:=f[j-b[i,1]-b[a[i,2],1]]+b[i,2]+b[a[i,2],2];


      if j-b[i,1]-b[a[i,2],1]-b[a[i,1],1]>=0 then
       if f[j]<f[j-b[i,1]-b[a[i,2],1]-b[a[i,1],1]]+b[i,2]+b[a[i,1],2]+b[a[i,2],2] then
       f[j]:=f[j-b[i,1]-b[a[i,2],1]-b[a[i,1],1]]+b[i,2]+b[a[i,1],2]+b[a[i,2],2];
      end;
      end;
   end;
for i:=1 to n do
if f[i]>ans then ans:=f[i];
writeln(ans*10);
close(input);
close(output);
end.