program chen;
var
	f,v,w,q,c:array[1..200000] of longint;
	i,j,m,n,s:longint;
begin
	assign(input,'budget.in');	reset(input);
	assign(output,'budget.out');	rewrite(output);
	readln(m,n,s);
	for i:=1 to n do begin
		readln(v[i],w[i],q[i]);
		if q[i]=0 then c[i]:=v[i]*w[i]
			else c[i]:=0;
	end;
	for i:=1 to n do 
		for j:=m downto v[i] do 
			if f[j-v[i]]+c[i]>f[j] then f[j]:=f[j-v[i]]+c[i];
	writeln(f[m]);
	close(input);	close(output);
end.