#include <bits/stdc++.h>
using namespace std;
int w[1005], v[1005], a[105][1005], f[1005];
int main() {
	int m,n;
	scanf("%d%d", &m,&n);
	
	for(int i = 1; i <= n; i++) {
		int p;
		
		scanf("%d%d%d", &w[i], &v[i],&p);
		a[p][++a[p][0]] = i;
	}
	if(m == 0) {
		printf("0");
		return 0;
	}
	
	for(int p = 1; p <= n; p++) {
		for(int i = m; i >= 0; i--) {
			for(int j = 1; j <= a[p][0]; j++) {
				if(i >= w[a[p][j]]) {
					int tmp = a[p][j];
					if(f[i-w[tmp]]+v[tmp] > f[i]) f[i] = f[i-w[tmp]]+v[tmp];
				}
			}
		}
	}
	printf("%d", f[m]);
	return 0;
}