60pts救~~~~

#include<bits/stdc++.h>
using namespace std;
const int MAXN=65,MAXM=32e2+5;
int n,m,v[MAXN],w[MAXN],f[MAXN],num[MAXN],dp[MAXM];
int main(){
	scanf("%d%d",&m,&n);
	m/=10;
	int step=1;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&v[i],&w[i],&f[i]);
		if(!f[i]){num[i]=step;step++;}
		v[i]/=10;w[i]*=v[i];
	}
	for(int i=1;i<=n;i++)
	    if(!f[i]){
	    	int l1=0,l2=0;
	    	for(int j=1;j<=n;j++) 
	    	    if(f[j]==num[i]){
	    	    	if(!l1&&!l2) l1=j;
	    	    	else l2=j;
				}
	    	for(int j=m;j>=v[i];j--){
	    		dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
				if(j-v[i]-v[l1]>=0) dp[j]=max(dp[j],dp[j-v[i]-v[l1]]+w[i]+w[l1]);
				if(j-v[i]-v[l2]>=0) dp[j]=max(dp[j],dp[j-v[i]-v[l2]]+w[i]+w[l2]);
				if(j-v[i]-v[l1]-v[l2]>=0) dp[j]=max(dp[j],dp[j-v[i]-v[l1]-v[l2]]+w[i]+w[l1]+w[l2]);
			}
		}
	printf("%d",dp[m]*10);
	return 0;
}