//=======================================================================================================================================================================================================================================================================================================================
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
int s,n; cin >> s >> n;
int v[n],w[n],k[n];
for(int i=1;i<=n;i++){
cin >> v[i] >> w[i] >> k[i];
}
vector<vector<int>> dp(n+5,vector<int>(s+5,0));
for(int i=0;i<=n;i++){
for(int j=0;j<=s;j++){
if(i==0 || j==0) {dp[i][j]=0; continue;}
for(int t=1;t<=k[i] && t*w[i]<=j;t++){
dp[i][j]=dp[i-1][j];
if(w[i] <= j) {
dp[i][j]=max(dp[i][j], dp[i-1][j-t*w[i]] + t*v[i]);
}
}
}
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=s;j++){
// cout << dp[i][j] << " ";
// } cout << endl;
// }
cout << dp[n][s] << endl;
}
