#include <bits/stdc++.h>
using namespace std;
bool cmp(const vector<long long> & a, const vector<long long> & b){
if (a[1]==b[1] and a[0]==b[0]){
return a[2]>b[2];
}
if (a[1]==b[1]){
return a[0]>b[0];
}
return a[1]>b[1];
}
int main(){
long long s,n; cin>>s>>n;
vector<vector<long long>> items(n);
for (long long i=0;i<n;i++){
long long x,y,z; cin>>x>>y>>z;
items[i]={x,y,z};
}
sort(items.begin(),items.end(),cmp);
vector<long long> dp(2*s,-1);
dp[0]=0;
for (auto j: items){
vector<long long> cnt(s+1,j[2]); //num remaining of this particular item, take max
for (long long i=0; i<s; i++){
if ((i+j[1]<=s) and (dp[i]!=-1) and (cnt[i]>0)){
if ((dp[i+j[1]]==-1) or (dp[i+j[1]]<(dp[i]+j[0]))){
dp[i+j[1]]=dp[i]+j[0];
cnt[i+j[1]]=cnt[i]-1;
} else if (dp[i+j[1]]==dp[i]+j[0]){
cnt[i+j[1]]=max(cnt[i+j[1]],cnt[i]-1);
}
}
}
}
long long ans=0;
for (auto i: dp){
ans=max(ans,i);
}
cout<<ans<<'\n';
}
