#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[65],imp[65],p[65];//重量 重要程度  对应主件 
int cnt[65];//cnt[i]表示i主件有多少个附件 
int dp[65][33000];//dp[i][j]表示i个物品用j个空间的最大值 
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>imp[i]>>p[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=dp[i-1][j];
			if(j-a[i]>=0){
				if(p[i]==0){
					if(dp[i][j]<dp[i-1][j-a[i]]+a[i]*imp[i]){
						dp[i][j]=dp[i-1][j-a[i]]+a[i]*imp[i];
					}
				}
				else{
					if(cnt[i]<=1&&dp[i][j]<dp[i-1][j-a[i]]+a[i]*imp[i]){
						cnt[i]++;
						dp[i][j]=dp[i-1][j-a[i]]+a[i]*imp[i];
					}
				}
			}
		}
	}
	cout<<dp[n][m];
}

求助神犇