#include <bits/stdc++.h>
using namespace std;
int main()
{
int s,n;
cin>>s>>n;
array<vector<array<int,2>>,2001> types;
for(int i=0;i<n;++i){
int v,w,k;
cin>>v>>w>>k;
if(w<=s){ types[w].push_back({v,k}); }
}
int dp[2001]{};
for(int w=0;w<=s;++w){
sort(types[w].rbegin(),types[w].rend());
auto it=types[w].begin();
int total_weight = 0;
int total_items = 0;
while(it != types[w].end() && (total_weight += w) <= s){
for(int j=s;j>=w;--j){
dp[j]=max(dp[j],dp[j-w]+it[0][0]);
}
if (++total_items == it[0][1]) {
++it;
total_items = 0;
total_weight = 0;
}
}
}
cout<<dp[s]<<'\n';
}
