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