#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define int long long
#define pll pair<int, int>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define FASTIO \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
int32_t main(){
//~ FASTIO
int s, n; cin >> s>>n;
int valt[n+1], weit[n+1], numt[n+1];
int val[n+1], wei[n+1], num[n+1];
int st[n]; iloop(1, n+1) st[i-1] = i;
iloop(0, n) {
cin >> valt[i+1] >> weit[i+1]>> numt[i+1];
//~ cin >> weit[i+1]>> valt[i+1];// >> numt[i+1];
}
wei[0] = -1;
sort(st, st+n, [&](int a, int b){
if (weit[a] == weit[b]){
return valt[a] > valt[b];
}
else return weit[a] < weit[b];
});
//iloop(0, n) cout << st[i] << " ";
iloop(1, n+1){
val[i] = valt[st[i-1]];
wei[i] = weit[st[i-1]];
num[i] = numt[st[i-1]];
}
//~ for(int i=1;i<=n;i++){
//~ cout<<val[i]<<" "<<wei[i]<<" "<<num[i]<<"\n";
//~ }
int csm = 0;
vector<pll> items;
iloop(1, n+1){
if (wei[i] != wei[i-1]) {
csm = 0;
}
while (csm <= s and num[i]){
items.pb({wei[i], val[i]});
num[i]--, csm+=wei[i];
}
}
int mem[2005];
fill(mem, mem+2005, 0);
//~ for(auto [w,v]:items){
//~ printf("%lld %lld\n",w,v);
//~ }
/*iloop(1, u+1){
cout << endl<< i << " " << wgt[i] << endl;
for (auto it : hm[i]) cout << it << " ";
cout << endl;
}
dg(u);*/
for(auto [w, v] : items){
for(int j=s;j>=1;j--){
mem[j]=max(mem[j], (j-w >=0?mem[j-w]+v:0));
}
}
/*iloop(0, u+1){
jloop(0, s+1) cout << mem[i][j] << " ";
cout << endl;
}*/
cout << mem[s];
}
