/*
Author: tminh_hk20
Task:
*/
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define getbit(x,y) ((x) & (1ll<<(y)));
#define turnon(x,y) ((x) | (1ll<<(y)));
#define turnoff(x,y) ((x) ^ (1ll<<(y)));
using namespace std;
const int N =1e5;
const int MOD = 998244353;
int n, s, v[N+10], w[N+10], k[N+10], f[2010], sl[2010];
vector<pii> p;
bool operator < (pii a, pii b){
return a.se<b.se;
}
void solve(){
cin>> s>> n;
for (int i=1;i<=n;i++) cin>> v[i]>> w[i]>> k[i];
for (int i=1;i<=n;i++){
int cur = 1;
while(k[i]>=cur && w[i]*cur<=s){
p.push_back({w[i]*cur,v[i]*cur});
k[i]-=cur;
cur*=2;
}
if (k[i]){
int x = min(k[i], s-cur);
p.push_back({w[i]*x,v[i]*x});
}
}
sort(p.begin(),p.end());
for (pii x: p){
int w, v; tie(w,v) = x;
if (++sl[w]>s/w+1) continue;
for (int i = s;i>=w;i--) f[i] = max(f[i], f[i-w]+v);
}
cout << f[s];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("CAULUONG.inp","r",stdin);
// freopen("CAULUONG.out","w",stdout);
int T = 1;
while(T--)solve();
}
