uses math;
var main:array[1..60] of boolean;
    v:array[1..60,0..2] of longint;
    w:array[1..60,0..2] of longint;
    now:array[1..10000] of longint;
    i,j,n,money,a,b,z:longint;

begin
    assign(input,'budgetb.in'); reset(input);
    assign(output,'budgetb.out'); rewrite(output);
    readln(money,n); money:=money div 10;
    fillchar(main,sizeof(main),false);
    fillchar(v,sizeof(v),0);
    fillchar(now,sizeof(now),0);
    for i:=1 to n do
    begin
    readln(a,b,z);
    if z=0 then begin main[i]:=true; v[i,0]:=a div 10; w[i,0]:=b; end else  begin
    if v[z,1]<>0 then begin v[z,2]:=a div 10; w[z,2]:=b; end else
    begin v[z,1]:=a div 10;  w[z,1]:=b; end; end;
    end;
    for i:=n downto 1 do
    if main[i] then begin
    for j:=money downto 0 do
    begin
    if j>=v[i,0] then now[j]:=max(now[j-v[i,0]]+v[i,0]*w[i,0],now[j]);
    if j>=v[i,0]+v[i,1] then now[j]:=max(now[j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1],now[j]);
    if j>=v[i,0]+v[i,2] then now[j]:=max(now[j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2],now[j]);
    if j>=v[i,0]+v[i,1]+v[i,2] then now[j]:=max(now[j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2],now[j]);
    end;
    end;
    writeln(now[money]*10);
    close(output);
    end.