#include <bits/stdc++.h>
using namespace std;

int m,n,ans=0,vol=0;

struct thing
{
	int mass;
	int value;
	int team;
}a[1010];

bool cmp(thing x,thing y)
{
	if((1.0*x.value/x.mass)>(1.0*y.value/y.mass))
	  return 1;
	else
	  return 0;
}

int main()
{
	bool flag[100010]={0};
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].mass>>a[i].value>>a[i].team;
		if(a[i].mass>m)
		{
		  i--;
		  n--;
	    }  
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(flag[a[i].team]==0&&vol+a[i].mass<=m)
		{
		  ans+=a[i].value;
		  vol+=a[i].mass;
		  flag[a[i].team]=1;
	    }
	}
	cout<<ans<<endl;
	return 0;
}

标签写的是动态规划&dp，我用的贪心+排序，不太懂怎么弄动态规划，求助QAQ