#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
bool cmp(pair<int,pair<int,int>>& a,pair<int,pair<int,int>>& b){
return a.second.first*b.second.second<b.second.first*a.second.second;
}
signed main(){
long long n,s,x,v,k;
cin>>s>>n;
vector<long long> dp(s+1);
dp[0]=0;
vector<pair<int,pair<int,int>>> elements(n);
for(int i=0;i<n;i++){
cin>>v>>x>>k;
elements[i]={k,{x,v}};
}
sort(elements.begin(),elements.end(),cmp);
int cur=1;
for(int i=0;i<n;i++){
//cout<<elements[i].second.first<<' '<<elements[i].second.second<<'\n';
int cnt=0,cnt2=0;
while(cnt<=s&&cnt2<elements[i].first&&cur<=s){
cnt+=elements[i].second.first;
cnt2++;
for(int j=s;j>=elements[i].second.first;j--){
dp[j]=max(dp[j],dp[j-elements[i].second.first]+elements[i].second.second);
}
}
}
long long ans=0;
for(int i=0;i<=s;i++){
ans=max(ans,dp[i]);
//cout<<dp[i]<<' ';
}
cout<<ans;
}
