#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int INF=1e9;
ll dp[2001][2001];
void solve()
{
int s,n;
cin >> s >> n;
map<int,vector<pair<int,int>>> bw;
for(int i=0;i<n;i++)
{
int v,w,k;
cin >> v >> w >> k;
if(w<=s&&k) bw[w].push_back({v,k});
}
for(int i=0;i<=(int)bw.size();i++) for(int j=0;j<=s;j++) dp[i][j]=-INF;
dp[0][0]=0;
int p=0;
for(map<int,vector<pair<int,int>>>::iterator it=bw.begin();it!=bw.end();it++)
{
p++;
int w=it->fi;
vector<pair<int,int>> temp=it->se;
sort(temp.begin(),temp.end(),greater<pair<int,int>>());
for(int i=0;i<=s;i++)
{
dp[p][i]=dp[p-1][i];
int c=0,t=0,cr=0;
ll pr=0;
while((c+1)*w<=i&&t<(int)temp.size())
{
c++;
pr+=temp[t].fi;
if(dp[p-1][i-c*w]!=-INF) dp[p][i]=max(dp[p][i],dp[p-1][i-c*w]+pr);
cr++;
if(cr==temp[t].se)
{
cr=0;
t++;
}
}
}
}
ll ans=-1e16;
for(int i=0;i<=s;i++) ans=max(ans,dp[p][i]);
cout << ans << endl;
}
int main()
{
fastIO
solve();
return 0;
}
