#include <bits/stdc++.h>
#define MAX 100001
#define MOD 1000000007
#define int long long
#define INF INT_MAX
using namespace std;
const int mod=998244353;
inline void USACO(string filename){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int n,s,dp[2001];
vector<vector<pair<int,int>>> a;
void solve(){
cin >> s >> n;
a.resize(s+1);
for(int i=0;i<n;i++){
int x,y,z;
cin >> x >> y >> z;
a[y].push_back({x,z});
}
dp[0]=0;
for(int i=1;i<=s;i++){
sort(a[i].rbegin(),a[i].rend());
dp[i]=-INF;
}
for(int i=1;i<=s;i++){
int cnt=s/i;
for(auto &x:a[i]){
while(cnt && x.second--){
for(int j=s;j>=i;j--){
if(dp[j-i]==-INF){
continue;
}
dp[j]=max(dp[j],dp[j-i]+x.first);
}
cnt--;
}
if(cnt==0){
break;
}
}
}
int mx=0;
for(int i=1;i<=s;i++){
mx=max(mx,dp[i]);
}
cout << mx;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
//USACO("palpath");
int t=1;
//cin >> t;
while(t--){
solve();
}
}
