#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()
{
/*
for(int i=2000;i<=10000000;i*=10)
{
int s=0;
for(int j=1;j<=i;j++)
s+=i/j;
cout<<i<<" "<<s<<" "<<s/i<<" "<< log2(i)<<endl;
}
*/
int s, n;
cin >> s >> n;
vector<int> v;
vector<int> w;
//vector<int> k;
vector<vector<ii>> vp(MAX, vector<ii>());
for(int i=1;i<=n;i++)
{
int ww, vv, kk;
cin >> vv >> ww >> kk;
vp[ww].push_back({-vv,kk});
}
for(int i=1;i<MAX;i++)
{
sort(vp[i].begin(),vp[i].end());
int mx = MAX/i;
for(int j=0;j<vp[i].size();j++)
{
while(vp[i][j].y && mx)
{
v.push_back(-vp[i][j].x);
w.push_back(i);
vp[i][j].y--;
mx--;
}
if(mx<=0) break;
}
}
int dp[2][s+1];
for(int i=0;i<2;i++)
{
for(int j=0;j<=s;j++)
dp[i][j]=0;
}
for(int i=0;i<v.size();i++)
{
//k = min(k, MAX);
for(int j=0;j<=s;j++)
{
//NOT TAKE
int nt = dp[(i+1)%2][j];
//TAKE
int m = 1;// = min(k, j/w);
int t = 0;
//for(m=0;m<=k;m++)
{
if(j>=m*w[i])
t = dp[(i+1)%2][j-m*w[i]]+v[i]*m;
//cout << t<< " - "<<nt<<" "<<m <<" "<<j<<" "<<w<<" "<<i<<endl;
dp[i%2][j] = max(dp[i%2][j],max(nt, t));
}
}
//for(int j=0;j<=s;j++)
//cout << dp[i%2][j]<<" ";
//cout<<endl;
}
cout << dp[(v.size()+1)%2][s];
return 0;
}
