#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
typedef vector<int> vi;
int n,S;
vi val,we,have;
int32_t main(){
ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
cin >> S >> n;
for (int i = 0; i < n; i++){
int v,w,k; cin >> v >> w >> k;
val.pb(v);
we.pb(w);
have.pb(k);
}
vi dp(S + 10,0);
for (int i = 0; i < n; i++){
vi ndp(S + 10,0);
for (int j = 0; j <= S; j++){
if (j != 0) ndp[j] = dp[j];
if (j != 0) ndp[j] = max(ndp[j],ndp[j-1]);
for (int k = 1; k <= have[i]; k++){
int w = k * we[i], v = k * val[i];
if (j - w < 0) break;
ndp[j] = max(ndp[j],dp[j - w] + v);
}
//cout << i << " " << j << ": " << dp[i][j] << endl;
}
dp = ndp;
}
cout << dp[S] << endl;
return 0;
}
