C++ :

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=40005,M=105;
struct node{
	int v,p,q,fn;
	int fv[2],fp[2];
};
node a[M];
int f[N]={0};
int n,m;
void init()
{

	cin>>n>>m;
	memset(a,0,(m+1)*sizeof(node));
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].v>>a[i].p>>a[i].q;
		if(a[i].q)
		{
			int k=a[a[i].q].fn;
			a[a[i].q].fv[k]=a[i].v;
			a[a[i].q].fp[k]=a[i].p;
			a[a[i].q].fn++;
		}
	}
}
int main()
{
	init();
	for(int i=1;i<=m;i++)
		if(a[i].q==0)
			for(int j=n;j>=a[i].v;j--)
			{
				f[j]=max(f[j],f[j-a[i].v]+a[i].v*a[i].p);
				if(a[i].fn>=1&&j>=a[i].v+a[i].fv[0])
				  f[j]=max(f[j],f[j-a[i].v-a[i].fv[0]]+a[i].v*a[i].p+a[i].fv[0]*a[i].fp[0]);
				if(a[i].fn>1&&j>=a[i].v+a[i].fv[1])
				  f[j]=max(f[j],f[j-a[i].v-a[i].fv[1]]+a[i].v*a[i].p+a[i].fv[1]*a[i].fp[1]);
				if(a[i].fn>1&&j>=a[i].v+a[i].fv[0]+a[i].fv[1])
				  f[j]=max(f[j],f[j-a[i].v-a[i].fv[0]-a[i].fv[1]]+a[i].v*a[i].p
					+a[i].fv[0]*a[i].fp[0]+a[i].fv[1]*a[i].fp[1]);
			}
	cout<<f[n]<<endl;
	return 0;
}

Pascal :

var
n,m:longint;
newv,newp:array[-1000..maxint] of longint;
v,p,q:array[-1000..maxint] of longint;
f:array[-1000..maxint] of longint;
function calc(k:longint):longint;
var
i,j,x:longint;
begin
x:=1;
newv[1]:=v[k];
newp[1]:=p[k];
for i:=1 to m do
if q[i]=k then
begin
for j:=1 to x do
begin
newv[j+x]:=newv[j]+v[i];
newp[j+x]:=newp[j]+p[i];
end;
x:=x*2;
end;
exit(x);
end;
procedure dp;
var
i,j,k,temp:longint;
begin
fillchar(f,sizeof(f),0);
for i:=1 to m do
begin
if q[i]<>0 then continue;
for j:=n downto 1 do
for k:=1 to calc(i) do
if j>=newv[k] then
if (f[j]<f[j-newv[k]]+newp[k]) then f[j]:=f[j-newv[k]]+newp[k];
end;
end;
procedure init;
var
i:longint;
begin
read(n,m);
for i:=1 to m do
begin
read(v[i],p[i],q[i]);
p[i]:=p[i]*v[i];
end;
end;
begin
init;
dp;
writeln(f[n]);
end.