#include<iostream> #include<vector> using namespace std; const int N = 1e3 + 10; int n, m, t, f[N][N], w[N], v[N], mg; vector<int> group[N]; int main(){ cin >> m >> n; for(int i = 1; i <= n; i++){ cin >> w[i] >> v[i] >> t; group[t].push_back(i); mg = max(mg, t); } for(int i = 1; i <= mg; i++){ for(int j = 1; j <= m; j++){ f[i][j] = f[i-1][j]; for(int k = 0; k < group[i].size(); k++){ if(j - w[group[i][k]] >= 0){ f[i][j] = max(f[i][j], f[i-1][j-w[group[i][k]]] + v[group[i][k]]); } } } } cout << f[mg][m]; return 0; }