#include<iostream>  
#include<cstdio>
#include<cmath>  
#include<cstring>  
#include<algorithm> 
using namespace std;
int m,n,a[61],f[32001],v[61],s[61],v1[10],a1[10],ans;
int main(){ 
    freopen("budget.in","r",stdin);        
    freopen("budget.out","w",stdout);   
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>a[i]>>s[i];
        a[i]*=v[i];
    }
    for(int i=1;i<=n;i++){
        if(!s[i]){
        	ans=1;
        	v1[1]=v[i];
        	a1[1]=a[i];
        	for(int j=1;j<=n;j++){
        		if(s[j]==i){
        			int p=ans;
        			for(int k=1;k<=p;k++){
        				ans+=1;
        				v1[ans]=v1[k]+v[j];
        				a1[ans]=a1[k]+a[j];
                    }
                }
            }
            for(int k=m;k>=0;k--)
            	for(int j=1;j<=ans;j++)
            		if(k>=v1[j])
            			f[k]=max(f[k],f[k-v1[j]]+a1[j]);
        }
    }
    cout<<f[m];
    return 0;
}