#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int wx = 2e3+5, nx = 1e5+5;
ll n,m,s,dp[2][wx];
priority_queue<pair<ll,ll>> items[wx];
vector<ll> w,vl;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>s>>n;
for(int i = 1; i <= n; i++)
{
ll v,w,k; cin>>v>>w>>k;
items[w].push({v,k});
}
for(int i = 1; i <= s; i++)
{
if(items[i].empty()) continue;
ll cnt = 0;
int mx = s/i;
while(!items[i].empty() && cnt < mx)
{
auto [v,k] = items[i].top();
items[i].pop();
for(int j = 1; j <= k && cnt <= mx; j++, cnt++) w.push_back(i), vl.push_back(v);
}
}
m = w.size();
for(int i = 0; i < m; i++)
{
int cur = i&1;
int prev = !cur;
for(int j = 1; j <= s; j++)
{
dp[cur][j]=dp[prev][j];
if(w[i]<=j) dp[cur][j]=max(dp[cur][j],dp[prev][j-w[i]]+vl[i]);
}
}
cout<<dp[(m-1)&1][s];
}
