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

int n,m,ap[61][32010],v[61],p[61],q[61];
vector<int> mas[61];

int main(){
	cin >> n >> m;
	
	int w[61];
	for(int i=1;i<=m;i++){
		cin >> v[i] >> p[i] >> w[i];
		q[i]=v[i]*p[i];
		if(w[i]) mas[w[i]].push_back(i);
	}
	
	for(int i=1;i<=m;i++){
		for(int j=10;j<=n;j+=10){
			ap[i][j]=max(ap[i-1][j],ap[i][j]);
			if(w[i]) continue;
	
			int y=ap[i][j];
			switch(mas[i].size()){
				case 0:
					if(j-v[i]>=0) y=max(y,ap[i-1][j-v[i]]+q[i]);
					break;	
				case 1:
					if(j-v[i]>=0) y=max(y,ap[i-1][j-v[i]]+q[i]);
					if(j-v[i]-v[mas[i][0]]>=0 && i>=2) y=max(y,ap[i-2][j-v[i]-v[mas[i][0]]]+q[i]+q[mas[i][0]]);
					break;
				case 2:
					if(j-v[i]>=0) y=max(y,ap[i-1][j-v[i]]+q[i]);
					
					if(j-v[i]-v[mas[i][0]]>=0 && i>=2){
						y=max(y,ap[i-2][j-v[i]-v[mas[i][0]]]+q[i]+q[mas[i][0]]);
					}
					
					if(j-v[i]-v[mas[i][1]]>=0 && i>=2){
						y=max(y,ap[i-2][j-v[i]-v[mas[i][1]]]+q[i]+q[mas[i][1]]);
					}
					
					if(j-v[i]-v[mas[i][0]]-v[mas[i][1]]>=0 && i>=3){
						y=max(y,ap[i-3][j-v[i]-v[mas[i][0]]-v[mas[i][1]]]+q[i]+q[mas[i][0]]+q[mas[i][1]]);
					}
					break;
			}		
			ap[i][j]=max(ap[i][j],y);
		}
	}
	
//	cout << "\t"; 
//	for(int j=200;j<=2000;j+=100) cout << j << "\t";
//	cout  << endl;
//	for(int i=1;i<=10;i++){
//		cout << i << ":\t";
//		for(int j=200;j<=2000;j+=100){
//			cout << ap[i][j] << "\t";
//		}
//		cout << endl;
//		}

	cout << ap[m][n] <<endl;	
	
	/* 
	8000 20
	100 3 0
	400 5 0
	300 5 0
	1400 2 2
	500 2 2
	800 2 3
	1400 5 0
	300 5 0
	1400 3 0
	500 2 0
	1800 4 0
	440 5 10
	1340 5 10
	1430 3 0
	500 2 0
	800 2 0
	1400 5 0
	300 4 0
	400 3 0
	500 3 18

	36400
	*/
}

实在看不出来什么问题