#include<bits/stdc++.h>
using namespace std;
long long N, S;
pair<int, pair<int, int> > a[100010];
vector<pair<int, int> > edge[20010];
vector<pair<int, int> > b;
int dp[20010];
int cnt[20010];
bool cmp(pair<int, int> x, pair<int, int> y){
return x.second>y.second;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin>>S>>N;
for(int i=1; i<=N; i++) cin>>a[i].second.first>>a[i].second.second>>a[i].first;
for(int i=1; i<=N; i++) edge[a[i].second.second].push_back(make_pair(a[i].second.first, a[i].first));
for(int i=1; i<=S; i++){
for(auto v:edge[i]){
for(int j=0; j<=12; j++){
if((1<<j)<=v.second){
v.second-=(1<<j);
if((long long)i*(1<<j)>S) break;
b.push_back(make_pair(i*(1<<j), v.first*(1<<j)));
}
}
if(v.second){
if((long long)i*v.second<=S) b.push_back(make_pair(i*v.second, v.first*v.second));
}
}
}
sort(b.begin(), b.end());
for(int i=1; i<=S; i++) dp[i]=-2e9;
sort(b.begin(), b.end(), cmp);
for(auto v:b){
cnt[v.first]++;
if(cnt[v.first]>S/v.first+1) continue;
for(int i=S; i>=0; i--){
if(i+v.first<=S){
dp[i+v.first]=max(dp[i+v.first], dp[i]+v.second);
}
}
}
int total=-2e9;
for(int i=0; i<=S; i++) total=max(total, dp[i]);
cout<<total;
}
