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

int n, m, q[61], p[61], dp[4001];
vector<int> v[61];

int main(){
	scanf("%d%d", &n, &m);
	n /= 10;
	for(int i = 1; i <= m; i++){
		int c;
		scanf("%d%d%d", &p[i], &q[i], &c);
		q[i] *= p[i];
		p[i] /= 10;
		if(c == 0){
			v[i].push_back(i);
		}else{
			v[c].push_back(i);
		}
	}
	for(int i = 1; i <= m; i++){
		if(v[i].size() != 0){
			for(int j = n; j >= 0; j--){
				if(v[i].size() >= 1){
					int x = v[i][0];
					if(j >= p[x])
					dp[j] = max(dp[j], dp[j - p[x]] + q[x]);
					if(v[i].size() >= 2){
						int x1 = v[i][1];
						if(j >= (p[x] + p[x1])){
							dp[j] = max(dp[j], dp[j - p[x] - p[x1]] + q[x] + q[x1]);
						}
						if(v[i].size() >= 3){
							int x2 = v[i][2];
							if(j >= (p[x] + p[x1] + p[x2])){
								dp[j] = max(dp[j], dp[j - p[x] - p[x1] - p[x2]] + q[x] + q[x1] + q[x2]);
							}
						}
					}
				}
			}
		}
	}
	printf("%d\n", dp[n]);
}

hack没过 求条