#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=5e4+5,S=2005,I=1e5+5;
int n,s,f[S],dp[N][S],m;
vector<int> a[I];
pair<int,int> b[N];
bool cmp(vector<int> x,vector<int> y){
if (x[1]!=y[1]) return x[1]>y[1];
else return x[0]>y[0];
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>s>>n;
for (int i=1;i<=s;i++) f[i]=s/i;
for (int i=1;i<=n;i++){
a[i].resize(3);
cin>>a[i][0]>>a[i][1]>>a[i][2];
}
sort(a+1,a+1+n,cmp);
for (int i=1;i<=n;i++){
while (a[i][2] && f[a[i][1]]){
m++;
b[m]={a[i][0],a[i][1]};
a[i][2]--;
f[a[i][1]]--;
}
}
swap(n,m);
dp[0][0]=0;
for (int i=1;i<=n;i++){
for (int j=0;j<=s;j++){
dp[i][j]=dp[i-1][j];
if (j-b[i].S>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-b[i].S]+b[i].F);
}
}
int ans=0;
for (int i=0;i<=s;i++) ans=max(ans,dp[n][i]);
cout<<ans<<endl;
return 0;
}
