#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N = 1e6 + 5;
int n,s;
int f[2005];
struct p{
int v,w,k;
};
p a[N];
vector<int> dsk[2005];
ii arr[N];
bool cmp(int i,int j){
return a[i].v > a[j].v;
}
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].v>> a[i].w>> a[i].k;
a[i].k = min(a[i].k,s);
dsk[a[i].w].push_back(i);
}
int dem = 0;
for(int i = 1; i <= s; i++){
int sl = 0;
sort(dsk[i].begin(),dsk[i].end(),cmp);
for(int j : dsk[i]){
sl += a[j].k;
int _sl = 1;
while(_sl <= a[j].k){
arr[++dem] = {_sl*a[j].v,_sl*a[j].w};
_sl*=2;
}
if(sl*i > s) break;
}
}
int tons = 0;
int ans = 0;
for(int i = 1; i <= dem; i++){
tons += arr[i].se;
for(int j = min(s,tons); j >= arr[i].se; j--){
f[j] = max(f[j],f[j-arr[i].se] + arr[i].fi);
ans = max(ans,f[j]);
}
}
cout<<ans;
}
