#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n,m,i,j,k,l,x,y,z,f[40000];
vector<int> a[100][3];
int main(){
	scanf("%d%d",&m,&n);
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		if(z==0) a[i][0].push_back(x),a[i][1].push_back(y);
		else a[z][0].push_back(x),a[z][1].push_back(y);
	}
	for(i=1;i<=n;i++)
		if(a[i][0].size()!=0)
			for(j=m;j>=a[i][0][0];j--)
				if(f[j-1]<f[j-a[i][0][0]]+a[i][0][0]*a[i][1][0]){
					f[j]=f[j-a[i][0][0]]+a[i][0][0]*a[i][1][0];
					for(k=1;k<a[i][0].size();k++)
						if(j+a[i][0][k]<=m)
							f[j+a[i][0][k]]=max(f[j+a[i][0][k]-1],f[j]+a[i][0][k]*a[i][1][k]);
				}
	printf("%d\n",f[m]);
	return 0;
}