#include<bits/stdc++.h>
using namespace std;
int N, S;
pair<int, pair<int, int> > a[100010];
vector<pair<int, int> > edge[20010];
vector<pair<int, int> > b;
int dp[20010];
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<=13; j++){
if((1<<j)<=v.second){
v.second-=(1<<j);
b.push_back(make_pair(i*(1<<j), v.first*(1<<j)));
}
}
if(v.second) 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]=-32;
for(auto v:b){
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=-32;
for(int i=0; i<=S; i++) total=max(total, dp[i]);
cout<<total;
}
