#include <algorithm>
#include <bits/stdc++.h>
#include <cctype>
using namespace std;
#define name "king2."
#define ll long long
#define vi vector<int>
const int N=1e7+5, mod=998244353, S=2005;
int n, s;
ll dp[S];
vector<pair<ll,ll>> ds[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen(name "in","r",stdin);
//freopen(name "out","w",stdout);
cin>>s>>n;
for (int i=1;i<=n;i++){
int v,w,c;
cin>>v>>w>>c;
ds[w].push_back({v, c});
}
for (int i=1;i<=s;i++){
sort(ds[i].begin(),ds[i].end(),greater<pair<int,int>>());
int wei=0;
ll nwei=0;
for(auto [val , sl] : ds[i]){
for (int o=1;o<=sl;o++){
wei += i;
if(wei > s) break;
for (int j=s;j>=i;j--)
dp[j] = max(dp[j] , dp[j - i] + val);
}
if(wei > s) break;
}
}
cout<<dp[s];
return 0;
}
