var
  v,p,s:array[0..1000] of longint;
  b:array[0..1000,0..5] of longint;
  a:array[0..1000,0..8] of longint;
  c:array[0..1000,0..8] of longint;
  f:array[0..100,0..40000] of longint;
  e,n,m,i,j,k,w:longint;
function max(a,b:longint):longint;
begin
  if a>b then
    max:=a
  else
    max:=b
end;
begin
  assign(input,'budgetb.in');assign(output,'budgetb.out');
  reset(input);rewrite(output);
  readln(m,n,e);
  for i:=1 to n do
    begin
      readln(v[i],p[i],s[i]);
      if s[i]<>0 then
        begin
          inc(b[s[i],0]);
          b[s[i],b[s[i],0]]:=i;
        end;
    end;
  w:=0;
  fillchar(a,sizeof(a),0);
  for i:=1 to n do
    if s[i]=0 then
      begin
        inc(w);
        a[w,1]:=v[i]*p[i];
        c[w,1]:=v[i];
        a[w,2]:=a[w,1]+v[b[i,1]]*p[b[i,1]];
        c[w,2]:=c[w,1]+v[b[i,1]];
        a[w,3]:=a[w,1]+v[b[i,2]]*p[b[i,2]];
        c[w,3]:=c[w,1]+v[b[i,2]];
        a[w,4]:=a[w,1]+v[b[i,1]]*p[b[i,1]]+v[b[i,2]]*p[b[i,2]];;
        c[w,4]:=v[i]+v[b[i,1]]+v[b[i,2]];
      end;
  for i:=1 to w do
    for j:=0 to m do
      begin
        f[i,j]:=f[i-1,j];
        for k:=1 to 4 do
          if j>=c[i,k] then
            f[i,j]:=max(f[i,j],f[i-1,j-c[i,k]]+a[i,k]);
      end;
  writeln(f[w,m]);
 close(input);close(output);
end.