#include <iostream> using namespace std; int n,m,a[1010],b[1010],c[110][1010],maxn; int f[1010]; int main() { cin>>m>>n; for (int i = 1; i <= n; i++) { int t; cin>>a[i]>>b[i]>>t; maxn = max(maxn,t); c[t][++c[t][0]] = i; } for (int i = 1; i <= maxn; i++) for (int j = m; j >= 0; j--) for (int k = 1; k <= c[i][0]; k++) if (j - a[c[i][k]] >= 0) f[j] = max(f[j],f[j - a[c[i][k]]] + b[c[i][k]]); cout<<f[m]; return 0; }