#include <bits/stdc++.h> using namespace std; const int N=2005; int n,m,dp[N]; vector <pair <int,int>> v1[N],v2; signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> m >> n; for(int i=1;i<=n;i++){ int v,w,k; cin >> v >> w >> k; v1[w].push_back({v,k}); } for(int i=1;i<N;i++) sort(v1[i].begin(),v1[i].end(),greater <pair <int,int>>()); for(int i=1;i<N;i++){ int idx=0; for(int j=1;j<=m/i;j++){ if(idx>=v1[i].size()) continue; v2.push_back({i,v1[i][idx].first}); v1[i][idx].second--; if(v1[i][idx].second==0) idx++; } } for(auto [w,v]:v2) for(int i=m;i>=1;i--) if(w<=i) dp[i]=max(dp[i],dp[i-w]+v); cout << dp[m]; }