#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define pb push_back
#define fi first
#define se second
#define debug(x) cerr << #x << " => " << x << endl
#define all(x) x.begin(),x.end()
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int s,n;cin>>s>>n;
ll v[n+1],w[n+1],k[n+1];
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>k[i];
ll dp[n+1][s+1];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=0;j<=s;j++)
{
int m=1;
dp[i][j]=max(dp[i][j],dp[i-1][j]);
while(m<=k[i] && j+w[i]*m<=s)
{
dp[i][j+w[i]*m]=max(dp[i][j+w[i]*m],dp[i-1][j]+v[i]*m);
m++;
}
}
// for(int j=0;j<=s;j++) cout<<dp[i][j]<<' ';cout<<'\n';
}
cout<<dp[n][s];
return 0;
}
