#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define pb push_back
#define ii pair<int,int>
#define f first
#define s second
const int N=2001;
const ll INF=1e18;
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
void solve() {
int n,x; cin>>x>>n;
ll h[n],p[n],k[n];
for(int i=0; i<n; i++) cin>>p[i]>>h[i]>>k[i];
vi nw[N];
for(int i=0; i<n; i++) {
int q=(int)log2(k[i]);
ll left=k[i]-(1<<q) + 1;
// cout<<k[i]<<" --> "<<q<<" "<<left<<"\n";
for(int j=0; j<q && ((1ll<<j)*h[i] <=x); j++) nw[(1ll<<j)*h[i]].pb((1ll<<j)*p[i]);
if(left && left*h[i] <=x) nw[left*h[i]].pb(left*p[i]);
}
for(int i=0; i<N;i++) if(nw[i].size()) {
sort(nw[i].begin(), nw[i].end(), greater<>());
// for(auto j:nw[i]) cout<<j<<" ";
// cout<<"\n";
}
ll dp[x+1]={0};
for(ll p=0; p<=x; p++) {
for(auto i:nw[p]) {
bool change=false;
for(ll j=x-p; j>=0; j--) if(dp[j+p] < dp[j]+i) {
dp[j+p] = dp[j]+i;
change=true;
}
if(!change) break;
}
}
ll ans=0;
for(int i=0; i<=x; i++) ans=max(ans, dp[i]);
cout<<ans<<"\n";
}
int main() {
// #ifndef ONLINE_JUDGE
// freopen("nocross.in","r",stdin);
// freopen("nocross.out","w",stdout);
// #endif
ios_base::sync_with_stdio(false), cin.tie(NULL);
int t = 1;
while (t--) solve();
return 0;
}
