type thing=record
      v,p,son:longint;
      s:array[1..10]of longint;
     end;
const fg:array[1..12]of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048);
var n,m,i,j,k,l,g,bw,bww,wb,pt,wbb:longint; a:array[1..60]of thing; b:array[1..60]of longint;
    f:array[1..32000]of longint;
begin
assign(input,'budgetb.in'); assign(output,'budget.out'); reset(input); rewrite(output);
 readln(n,m,g); for i:=1 to m do a[i].son:=0; n:=n div 10;
 for i:=1 to m do
  begin
   readln(a[i].v,a[i].p,j); a[i].v:=a[i].v div 10;
   if j=0 then begin inc(pt); b[pt]:=i; end
   else begin inc(a[j].son); a[j].s[a[j].son]:=i; end;
  end;
 for i:=1 to pt do
  begin
   wbb:=b[i];
   for j:=0 to fg[a[wbb].son+1]-1 do
    begin
     k:=0; l:=0;
     bw:=j;
     while bw<>0 do
      begin
       bww:=bw and -bw;
       k:=k+a[a[wbb].s[bww]].v;
       l:=l+a[a[wbb].s[bww]].v*a[a[wbb].s[bww]].p;
       bw:=bw-bww;
      end;
     for wb:=n downto a[wbb].v+k do
      if f[wb]<f[wb-a[wbb].v-k]+l+a[wbb].v*a[wbb].p then f[wb]:=f[wb-a[wbb].v-k]+l+a[wbb].v*a[wbb].p;
    end;
  end;
 write(f[n]*10);
close(input); close(output); 
end.