Program t6;
  Var f:array [0..32000] of longint;
      a:array [1..3,1..60] of longint;
      b:array [1..4,1..60,1..2] of longint;
      t:array [1..60] of integer;
      n,i,j,m,len,k:longint;
  Function max(a,b:longint):longint;
  Begin
    if a>b then max:=a else max:=b;
  end;
  Begin
    readln(n,m);
    For i:=1 to m do begin
      readln(a[1,i],a[2,i],a[3,i]);
      a[2,i]:=a[2,i]*a[1,i];
      if a[3,i]=0 then begin
         b[1,i,1]:=a[1,i]; b[1,i,2]:=a[2,i];
         t[i]:=1;
      end else begin
        inc(t[a[3,i]]);
        b[t[a[3,i]],a[3,i],1]:=b[1,a[3,i],1]+a[1,i];
        b[t[a[3,i]],a[3,i],2]:=b[1,a[3,i],2]+a[2,i];
      end;
    end;
    For i:=1 to m do if t[i]=3 then begin
      inc(t[i]);
      b[4,i,1]:=b[2,i,1]+b[3,i,1]-b[1,i,1];
      b[4,i,2]:=b[2,i,2]+b[3,i,2]-b[1,i,2];
    end;
    For i:=1 to m do
      if t[i]<>0 then
        For j:=n downto b[1,i,1] do
          For k:=1 to t[i] do
            if j>=b[k,i,1] then f[j]:=max(f[j],f[j-b[k,i,1]]+b[k,i,2]);
    Writeln(f[n]);
  end.                                    
/**************************************************************
	Problem: 2265
	User: admin
	Language: Pascal
	Result: Wrong Answer
****************************************************************/