var tr:array[0..100]of record l,r:longint;end;
    v:array[0..100,0..32000]of boolean;
    f:array[0..100,0..32000]of longint;
    w,zhong:array[0..100]of longint;
    i,m,n,p,s:longint;
procedure dfs(x,y:longint);
var  max,te,k:longint;
begin
 if (v[x,y]) or (x=-1) then exit;
 dfs(tr[x].r,y);max:=f[tr[x].r,y];
 for k:=w[x] to y do
  begin
   dfs(tr[x].l,k-w[x]);dfs(tr[x].r,y-k);
   te:=f[tr[x].l,k-w[x]]+f[tr[x].r,y-k]+zhong[x]*w[x];
   if te>max then max:=te;
  end;
 f[x,y]:=max;v[x,y]:=true;
end;
begin
 assign(input,'budgetb.in');assign(output,'budgetb.out');
 reset(input);rewrite(output);
 readln(m,n,s);m:=m div 10;
 for i:=0 to n do begin tr[i].l:=-1;tr[i].r:=-1;end;
 for i:=1 to n do
  begin
   readln(w[i],zhong[i],p);w[i]:=w[i] div 10;
   if tr[p].l=-1 then tr[p].l:=i
    else begin tr[i].r:=tr[tr[p].l].r;tr[tr[p].l].r:=i;end;
  end;
 dfs(0,m);
 write(f[0,m]*10);  close(output); 
end.