var a,p:array[-100..2000,-100..2000] of int64；
q,jz,z,d,e,f:array[-1000..1000000] of int64；
zq,i,j,k,l,m,n,o,r,s,t,y,x:longint；
begin
read(zq,n)；
for i:=1 to n do
read(q[i],jz[i],z[i])；k:=0；
for i:=1 to n do
if z[i]=0 then begin
inc(k)；d[i]:=k；a[k,0]:=q[i]*jz[i]；p[k,0]:=q[i]；end；
for i:=1 to n do begin
if z[i]<>0 then
begin
inc(e[z[i]])；
a[z[i],e[z[i]]]:=a[z[i],0]+q[i]*jz[i]；
p[z[i],e[z[i]]]:=p[z[i],0]+q[i]；
if e[z[i]]=2 then begin
a[z[i],3]:=a[z[i],1]+q[i]*jz[i]；
p[z[i],3]:=p[z[i],1]+q[i]；end；end；end；
for i:=1 to k do
for j:=zq downto 0 do
for l:=0 to 3 do
if j>=p[i,l] then
if f[j]<=f[j-p[i,l]]+a[i,l] then
f[j]:=f[j-p[i,l]]+a[i,l]；
write(f[zq])；end.
供鄙视..
program jmysfa；
var
a,b,c:longint；
i,j,m,n:longint；
v,p:array[1..60]of longint；
fsv,fsp:array[1..60,1..3]of longint；
ff:array[0..60,0..33000]of longint；
function maxff(m1,m2,m3,m4,m5:longint):longint；
begin
if m2>m1 then m1:=m2；
if m4>m3 then m3:=m4；
if m3>m1 then m1:=m3；
if m5>m1 then m1:=m5；
maxff:=m1；
end；
begin
readln(m,n)；
fillchar(fsv,sizeof(fsv),0)；
fillchar(fsp,sizeof(fsp),0)；
for i:=1 to n do
begin
readln(a,b,c)；
if c=0 then begin v[i]:=a； p[i]:=b； end
else
begin
if fsv[c,1]<>0 then
begin
fsv[c,2]:=a；
fsp[c,2]:=b；
end
else
begin
fsv[c,1]:=a；
fsp[c,1]:=b；
end；
end；
end；
for i:=1 to n do
for j:=0 to m do
begin
if j>=v[i]+fsv[i,1]+fsv[i,2] then
ff[i,j]:=maxff(ff[i-1,j],ff[i-1,j-v[i]]+p[i]*v[i],ff[i-1,j-v[i]-fsv[i,2]]+p[i]*v[i]+fsp[i,2]*fsv[i,2],ff[i-1,j-v[i]-fsv[i,1]]+p[i]*v[i]+fsv[i,1]*fsp[i,1],ff[i-1,j-v[i]-fsv[i,1]-fsv[i,2]]+p[i]*v[i]+fsp[i,1]*fsv[i,1]+fsp[i,2]*fsv[i,2])
else
if j>=v[i]+fsv[i,1] then
ff[i,j]:=maxff(ff[i-1,j],ff[i-1,j-v[i]-fsv[i,1]]+p[i]*v[i]+fsp[i,1]*fsv[i,1],-maxlongint,-maxlongint,-maxlongint)
else
if j>=v[i]+fsv[i,2] then
ff[i,j]:=maxff(ff[i-1,j],ff[i-1,j-v[i]-fsv[i,2]]+p[i]*v[i]+fsp[i,2]*fsv[i,2],-maxlongint,-maxlongint,-maxlongint)
else
if j>=v[i] then
ff[i,j]:=maxff(ff[i-1,j],ff[i-1,j-v[i]]+p[i]*v[i],-maxlongint,-maxlongint,-maxlongint)
else
ff[i,j]:=ff[i-1,j]；
end；
writeln(ff[n,m])；
end.
jl:array[1..60] of integer；
f:array[0..32000] of longint；
k,i,j,m,n,v,d,p,l:longint；
begin(读入)
read(m,n)；
for i:=1 to n do begin
read(v,d,l)；
if l=0 then begin
a[i,0]:=v；b[i,0]:=v*d； end
else
begin
if a[l,1]<>0 then begin
a[l,2]:=v+a[l,0]；
b[l,2]:=v*d+b[l,0]；
jl[l]:=2；
end
else begin
a[l,1]:=v+a[l,0]；
b[l,1]:=v*d+b[l,0]；
jl[l]:=1；
end；
end；
end；
(处理主附件)
for i:=1 to n do
if (a[i,1]<>0)and(a[i,2]<>0)and(a[i,0]<>0) then begin
a[i,3]:=a[i,1]+a[i,2]-a[i,0]；
b[i,3]:=b[i,1]+b[i,2]-b[i,0]；
jl[i]:=3； end；
for i:=1 to n do if a[i,0]<>0 then
for j:=m downto 0 do
for p:=0 to jl[i] do
if (b[i,p]+f[j-a[i,p]]>=f[j])and(j-a[i,p]>=0) then
f[j]:=b[i,p]+f[j-a[i,p]]；
write(f[m])；
end.