#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct item {
ll val, wt, k;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int s, n;
cin >> s >> n;
vector<bool> pos(s+1,0); pos[0] = 1;
vector<ll> v(s+1,0);
vector<item> it(n);
for(int i=0; i<n; i++) {
cin >> it[i].val >> it[i].wt >> it[i].k;
}
vector<ll> val(s+1,-1); val[0] = 0;
ll mx = 0;
for(ll i=0; i<n; i++) {
for(ll j=s-it[i].wt; j>=0; j--) {
if(val[j] != -1) {
for(ll m=1; m<=it[i].k; m++) {
if(m*it[i].wt <= s) {
val[j+(m*it[i].wt)] = max(val[j+(m*it[i].wt)], val[j]+(m*it[i].val));
//mx = max(mx,val[j+(m*it[i].wt)]);
}
else break;
}
}
}
}
for(int i=1; i<=s; i++) mx = max(mx,val[i]);
cout << mx << "\n";
return 0;
}
