20分代码：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,m,a[1010],b[1010],c[1010],dp[1010],f[1010],p[1010];

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	cin>>a[i]>>b[i]>>c[i];
	
	for(int i=1;i<=m;i++)
	for(int j=n;j>=b[i];j--)
	{
		if(f[c[i]]==0)
		{
			if(dp[j-b[i]]+a[i]>dp[j])
			{
				dp[j]=dp[j-b[i]]+a[i];
				p[i]=a[i];
				f[c[i]]=1;
			}
		}
		else
		{
			if(dp[j-b[i]]-p[i]+a[i]>dp[j])
			{
				dp[j]=dp[j-b[i]]-p[i]+a[i];
				p[i]=a[i];
			 } 
		}
	}
	
	cout<<dp[n];
	
	return 0;
}