var
 f:array[0..32100]of longint;
 v,w:array[0..60,0..2]of longint;
 i,j,k,l,m,n,t,p:longint;

function max(a,b:longint):longint;
 begin
  if a>b then exit(a) else exit(b);
 end;

begin
 assign(input,'budgetb.in');reset(input);
 assign(output,'budgetb.out');rewrite(output);
 read(m,t,l);
 for i:=1 to t do
  begin
   read(j,k,l);
   if l=0 then 
    begin
     v[i,0]:=j*k;
     w[i,0]:=j;
     continue;
    end;
   if v[l,1]=0 then p:=1 else p:=2; 
   v[l,p]:=j*k;
   w[l,p]:=j;
  end;
 
 for i:=1 to t do
  for j:=m downto 0 do
   begin
    if j>=w[i,0] then f[j]:=max(f[j],f[j-w[i,0]]+v[i,0]);
    if j>=w[i,0]+w[i,1] then f[j]:=max(f[j],f[j-w[i,0]-w[i,1]]+v[i,0]+v[i,1]);
    if j>=w[i,0]+w[i,2] then f[j]:=max(f[j],f[j-w[i,0]-w[i,2]]+v[i,0]+v[i,2]);
    if j>=w[i,0]+w[i,1]+w[i,2] then f[j]:=max(f[j],f[j-w[i,0]-w[i,1]-w[i,2]]+v[i,0]+v[i,1]+v[i,2]);
   end;
 
 writeln(f[m]);
 close(input);close(output);
end.