#include <bits/stdc++.h>
#define NMAX 100000
#define SMAX 2000
using namespace std;
vector<pair<int, int>> have_weight[SMAX+1];
int dp[SMAX+1];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
for(int i=1; i<=n; i++)
{
int v, w, k;
cin >> v >> w >> k;
have_weight[w].push_back({v, k});
}
for(int w=1; w<=s; w++)
{
sort(have_weight[w].begin(), have_weight[w].end());
int cnt=s/w;
while(cnt>0 && !have_weight[w].empty())
{
auto [v, k]=have_weight[w].back();
if(k==0) have_weight[w].pop_back();
else
{
for(int i=s; i>=w; i--)
dp[i]=max(dp[i], dp[i-w]+v);
k--; cnt--;
have_weight[w].back()={v, k};
}
}
}
int ans=0;
for(int i=1; i<=s; i++)
{
ans=max(ans, dp[i]);
}
cout << ans;
return 0;
}
