#include <bits/stdc++.h>
using namespace std;
#define yon(x) cout<<((x)?"YES\n":"NO\n");
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define em emplace_back
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=k;i>=j;i--)
#define forp(x,y,a) for(auto &[x,y]:(a))
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;
typedef vector<vl> vvl;
typedef vector<vpl> vvpl;
typedef vector<string> vs;
typedef deque<ll> dl;
const int mod=1e9+7;
ll inf =1e18+1;
const int M=1e6;
const int N=1e3+1;
const ll dx[]={1,0,-1,0},dy[]={0,1,0,-1};
void solve(){
ll n,s;
cin>>s>>n;
vl dp(s+1,-inf),a(n),b(n),c(n);
vvpl g(s+1);
rep(i,0,n-1){
cin>>a[i]>>b[i]>>c[i];
if(c[i]){
g[b[i]].em(a[i],c[i]);
}
}
rep(i,0,s)sort(all(g[i]));
vpl k;
rep(i,1,s){
ll rem=s/i;
//cout<<rem<<"\n";
while(!g[i].empty()&&rem>0){
ll val=g[i].back().ff,cnt=g[i].back().ss;
g[i].pop_back();
rep(j,1,min(rem,cnt))k.em(val,i);
rem-=min(rem,cnt);
}
}
dp[0]=0;
for(auto &[x,y]:k){
//cout<<x<<" "<<y<<endl;
per(j,y,s){
dp[j]=max(dp[j-y]+x,dp[j]);
}
}
cout<<*max_element(all(dp));
}
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef Usaco
string f="herding";
freopen((f+".in").c_str(),"r",stdin);
freopen((f+".out").c_str(),"w",stdout);
#endif
int t = 1;
//cin >> t;
while (t--) {
solve();
// if(t>0)
//cout<<endl;
}
}
/*
*/
