#include <bits/stdc++.h>
//#define int long long
#define ii pair<int,int>
#define x first
#define y second
#define SYNC ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lef (idx*2)+1
#define rig (idx*2)+2
#define mid (l+r)/2
#define MAX 2003
using namespace std;
int32_t main()
{
int s, n;
cin >> s >> n;
int v[n];
int w[n];
int k[n];
int dp[n+1][s+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=s;j++)
dp[i][j]=0;
}
for(int i=1;i<=n;i++)
{
int w, v, k;
cin >> v >> w >> k;
k = min(k, (int)MAX);
for(int j=0;j<=s;j++)
{
//NOT TAKE
int nt = dp[i-1][j];
//TAKE
int m;// = min(k, j/w);
int t = 0;
for(m=0;m<=k;m++)
{
if(j>=m*w)
t = dp[i-1][j-m*w]+v*m;
//cout << t<< " - "<<nt<<" "<<m <<" "<<j<<" "<<w<<" "<<i<<endl;
dp[i][j] = max(dp[i][j],max(nt, t));
}
}
}
cout << dp[n][s];
return 0;
}
