var
n,m,i,j,k,c,t,s:longint;
f:array[0..32000] of longint;
a,b,num:array[0..60] of longint;
v,w,d:array[0..60,0..4] of longint;
begin
assign(input,'budget.in');
reset(input);
assign(output,'budget.out');
rewrite(input);
fillchar(f,sizeof(f),0);
fillchar(num,sizeof(num),0);
fillchar(d,sizeof(d),0);
for i:=0 to 60 do d[i,0]:=-1;
a[0]:=0;b[0]:=0;
readln(n,m,s);
for i:=1 to m do
begin
readln(a[i],b[i],c);
b[i]:=a[i]*b[i];
if c<>0 then
begin
inc(num[c]);
d[c,num[c]]:=i;
end
 else
d[i,0]:=0;
end;

t:=0;
for i:=1 to m do
if d[i,0]=0 then
begin
inc(t);
v[t][1]:=a[i];w[t][1]:=b[i];
v[t][2]:=a[i]+a[d[i,1]]; w[t][2]:=b[i]+b[d[i,1]];
v[t][3]:=a[i]+a[d[i,2]]; w[t][3]:=b[i]+b[d[i,2]];
v[t][4]:=a[i]+a[d[i,1]]+a[d[i,2]]; w[t][4]:=b[i]+b[d[i,1]]+b[d[i,2]];
end;

for i:=1 to t do
for j:=n downto 1 do
begin
for k:=1 to 4 do
if (v[i,k]<=j) and (f[j]<f[j-v[i,k]]+w[i,k]) then
f[j]:=f[j-v[i,k]]+w[i,k];
end;

writeln(f[n]);
close(input);
close(output);
end.