#include "bits/stdc++.h"
using namespace std;
//cycle edges = total edges-bridge edges
// adding cycle edges does not decrease the number of disconnected component but bridge edges do
// decreasing order of weight of edges . adding using dsu -> edges whoes parent already in the component is the cycle edges->can be found the min. weight prsent in cycle
const int md=1e9+7;
int main()
{
int s,n;
cin>>s>>n;
vector<int> val(n+1),we(n+1),no(n+1);
for(int i=1;i<=n;i++){
cin>>val[i]>>we[i]>>no[i];
}
vector<vector<long> > dp(n+1,vector<long>(s+1,0));
for(int i=1;i<=n;i++)
{
for(int j=0;j<=s;j++){
dp[i][j]=dp[i-1][j];
for(int k=1;k<=no[i];k++){
if(j>=k*we[i]){
dp[i][j]=max(dp[i][j],dp[i-1][j-k*we[i]]+k*val[i]);
}
}
}
}
cout<<dp[n][s]<<endl;
return 0;
}
