#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];
}
