#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;
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;
for (int j = 0; j < k; j++){
val.pb(v);
we.pb(w);
}
}
n = val.size();
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 (i != 0) ndp[j] = dp[j];
if (j != 0) ndp[j] = max(ndp[j],ndp[j-1]);
if (j - we[i] >= 0){
int last = 0;
if (i != 0) last = dp[j - we[i]];
ndp[j] = max(ndp[j],last + val[i]);
}
//cout << i << " " << j << ": " << dp[i][j] << endl;
}
dp = ndp;
}
cout << dp[S] << endl;
return 0;
}
