#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
ll s,n;cin>>s>>n;
map<ll,vector<pair<ll,ll>>>diff_wts;
for(ll i=1;i<=n;i++){
ll v,w,k;
cin>>v>>w>>k;
diff_wts[w].push_back({v,k});
}
vector<vector<ll>>dp(diff_wts.size()+1,vector<ll>(s+1));
dp[0][0]=0;
ll i=1;
for(auto &val:diff_wts){
ll wt=val.first;
vector<pair<ll,ll>>item_info=val.second;
sort(item_info.begin(),item_info.end(),greater<pair<ll,ll>>());
for(ll j=0;j<=s;j++){
dp[i][j]=dp[i-1][j];
ll copies=0;
ll type_at=0;
ll curr_used=0;
ll profit=0;
while(type_at < item_info.size() && j -(copies+1)*wt >=0){//j -(copies+1)*wt >=0 ye wali condn while loop k saath mein hi likhi jayegi agr hmm andar likhege toh wo infine loop mein phas jayega nad output nhi dega so writeoutside
copies++;//yeh copies always increase until in while loop
profit += item_info[type_at].first; //profit also getting increase until in while loop
dp[i][j]=max(dp[i][j] ,dp[i-1][j -copies*wt]+profit);
curr_used++;//to check for one type completion so that move to another type
if(curr_used==item_info[type_at].second){
type_at++;//move to next type means move to next pair of item_info
curr_used=0;
}
}
}
i++;
}
//cout<<dp[diff_wts.size()][s];
//auto it=*max_element(dp.back().begin(), dp.back().end());
cout<<dp[diff_wts.size()][s];
}
