#include <bits/stdc++.h>
#define f1(x , y) for(register int i = x ; i <= y ; i++)
#define f2(x , y) for(register int j = x ; j <= y ; j++)
#define ri register int
#define ll long long
#define il inline
#define cs const
using namespace std;

il int rd(){
    int out = 0 , flag = 1; char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0'; c = getchar();}
    return flag * out;
}

cs int N = 6e1 + 10 , M = 3.2e4 + 10;
int n , m , f[M] , x , y;
struct node{int h , u , p , q;}w[N];
vector <int> p[N];

int main(){
	n = rd() , m = rd();
	f1(1 , m) w[i].h = i , w[i].u = rd() , w[i].p = rd() , w[i].q = rd();
	f1(1 , m){if(w[i].q){p[w[i].q].push_back(i); if(p[w[i].q].size() == 3) p[w[i].q].push_back(-1);} else p[i].push_back(i);}
	for(int k = 1 ; k <= m ; k++){
		if(p[k].empty()) continue;
		for(int i = n ; i >= 0 ; i--)
			f2(0 , p[i].size() - 1){
				if(j == 0) x = w[i].u * w[i].p , y = w[i].u;
				if(j == 1 || j == 2) x = w[p[i][j]].u * w[p[i][j]].p + w[i].u * w[i].p , y = w[p[i][j]].u + w[i].u;
				if(j == 3) x = w[p[i][1]].u * w[p[i][1]].p + w[p[i][2]].u * w[p[i][2]].p + w[i].u * w[i].p , y = w[p[i][1]].u + w[p[i][2]].u + w[i].u;
				if(i < y) continue;
				f[i] = max(f[i] , f[i - y] + x);
			}
	}cout << f[n];
	return 0;
}