#include<cstdio>
#include<windows.h>
int v,n;
int a[61],c[61],q[61];
bool p[61]={true};
int dp[32001];
int main() {
	scanf("%d%d",&v,&n);
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d",a+i,c+i,q+i);
		c[i]=c[i]*a[i];
	}
	for(int i=1;i<=n;i++) {
		for(int j=v;j>=0;j--) {
			if(j>=a[i]) {
				if(p[q[i]]) {
					if(dp[j]<=dp[j-a[i]]+c[i]) {
						dp[j]=dp[j-a[i]]+c[i];
						p[i]=true;
					}
				}
			}
		}
	}
	printf("%d",dp[v]);
	return 0;
}