#include<bits/stdc++.h> #define int long long using namespace std; vector <int> vec[1005]; int w[1005],v[1005],dp[1005][1005]; signed main(){ int n,m,c,t = 0; cin>>m>>n; for (int i = 1;i <= n;i++){ cin>>w[i]>>v[i]>>c; t = max(t,c); vec[c].push_back(i); } for (int i = 1;i <= t;i++){ for (int j = m;j >= 0;j--){ dp[i][j] = dp[i - 1][j]; for (int k = 0;k < vec[i].size();k++){ int l = vec[i][k]; //cout<<l<<' '<<j<<' '<<w[l]<<' '<<v[l]<<'\n'; if (j >= w[l]){ dp[i][j] = max(dp[i][j],dp[i - 1][j - w[l]] + v[l]); //cout<<dp[i][j]<<'\n'; } } } } cout<<dp[t][m]; return 0; }