#include<bits/stdc++.h>
using namespace std;
int money,n,v,p,q;
int main_w[34005],main_v[34005];
int node_w[34005][3],node_v[34005][3];
int f[34005];
int main()
{
	scanf("%d %d",&money,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d %d",&v,&p,&q);
		if(q==0)
		{
			main_w[i]=v;
			main_v[i]=v*p; 
		}
		else
		{
			node_w[i][0]++;
			node_w[i][node_w[i][0]]=v;
			node_v[i][node_w[i][0]]=v*p;
		}
	}
	for(int i=1;i<=n;i++)
	{
        for(int j=money;main_w[i]!=0&&j>=main_w[i];j--)
		{
            f[j]=max(f[j],f[j-main_w[i]]+main_v[i]);
            if(j>=main_w[i]+node_w[i][1])
                f[j]=max(f[j],f[j-main_w[i]-node_w[i][1]]+main_v[i]+node_v[i][1]);
            if(j>=main_w[i]+node_w[i][2])
                f[j]=max(f[j],f[j-main_w[i]-node_w[i][2]]+main_v[i]+node_v[i][2]);
            if(j>=main_w[i]+node_w[i][1]+node_w[i][2])
                f[j]=max(f[j],f[j-main_w[i]-node_w[i][1]-node_w[i][2]]+main_v[i]+node_v[i][1]+node_v[i][2]);
		}
	}
	printf("%d\n",f[n]);
	return 0;
}

看不出来什么问题啊