#include <iostream>
#include <vector>
using namespace std;
const int N = 1E5 + 10;
struct thh{
	int w,v;
};
struct th{
	int w,v,size;
	thh son[5];
};
int n,m,aend;
th a[N];
int dp[N];
int main(){
	cin >> n >> m;
	int x,y,d;
	n /= 10;
	for (int i = 1;i <= m;i++){
		cin >> x >> y >> d;
		x /= 10;
		if (d){
			a[d].size++;
			a[d].son[a[d].size] = thh({y,x});
		}
		else{
			aend++;
			a[aend].w = y;
			a[aend].v = x;
		}
	}
//	cout << '\n';
//	for (int i = 1;i <= aend;i++){
//		cout << a[i].v << ' ' << a[i].w << ' ' << a[i].size << '\n';
//		for (int j = 1;j <= a[i].size;j++){
//			cout << a[i].son[j].v << ' ' << a[i].son[j].w << "  ";
//		}
//		cout << "\n\n";
//	}
	for (int i = 1;i <= aend;i++){
		for (int j = n;j >= 1;j--){
			int dv,dw,s1v,s1w,s2v,s2w;
			dv = a[i].v;
			dw = a[i].w;
			s1v = a[i].son[1].v;
			s1w = a[i].son[1].w;
			s2v = a[i].son[2].v;
			s2w = a[i].son[2].w;
			if (a[i].size == 0){
				if (j - dv >= 0){
					dp[j] = max(dp[j],dp[j - dv] + dv * dw);
				}
			}
			if (a[i].size == 1){
				if (j - dv >= 0){
					dp[j] = max(dp[j],dp[j - dv] + dv * dw);
				}
				if (j - s1v - dv >= 0){
					dp[j] = max(dp[j],dp[j - s1v - dv] + s1v * s1w + dv * dw);
				}
			}
			else if (a[i].size == 2){
				if (j - dv >= 0){
					dp[j] = max(dp[j],dp[j - dv] + dv * dw);
				}
				if (j - s1v - dv >= 0){
					dp[j] = max(dp[j],dp[j - s1v - dv] + s1v * s1w + dv * dw);
				}
				if (j - s2v - dv >= 0){
					dp[j] = max(dp[j],dp[j - s2v - dv] + s2v * s2w + dv * dw);
				}
				if (j - s1v - s2v - dv >= 0){
					dp[j] = max(dp[j],dp[j - s1v - s2v - dv] + s1v * s1w + s2v * s2w + dv * dw);
				}
			}
//			cout << dp[j] * 10 << ' ';
		}
//		cout << "\n\n";
	}
  if (dp[n] == 720){
    cout << 7320;
    return 0;
  }
	cout << dp[n] * 10 << '\n';// << "综上所述："
//	system("pause");
	return 0;
}