#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>>ob[2005];
vector<pair<int,int>>rob;
int dp[2005];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int s,n;cin>>s>>n;
for(int i=1;i<=n;i++){
int v,w,k;cin>>v>>w>>k;
ob[w].push_back({v,k});
}
for(int i=1;i<=2000;i++){
sort(ob[i].begin(),ob[i].end(),greater<pair<int,int>>());
if(ob[i].size()>0){
int mx=2000/i+1;
for(auto x:ob[i]){
int val=min(mx,x.second);
x.second-=val;
mx-=val;
for(int j=0;j<val;j++)rob.push_back({x.first,i});
if(mx==0)break;
}
}
}
dp[0]=0;
for(auto [v,w]:rob){
//cerr<<v<<" "<<w<<"\n";
for(int i=2000;i>=0;i--){
int from=i-w;
if((from<0||dp[from]==0)&&from)continue;
dp[i]=max(dp[i],dp[from]+v);
}
}
int ans=0;
for(int i=0;i<=s;i++)ans=max(ans,dp[i]);
cout<<ans;
}
