#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(x) x.begin(),x.end()
#define vpii vector<pair<int,int>>
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef map<int,int> mii;
const int Prime1= 1000000007;
const int Prime2= 998244353;
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1){
res = res * a % m;}
a = a * a % m;
b >>= 1;
}
return res;
}
vector<int> hp(int n){
vector<int>h(n,0) ;
for(int i=2;i<n;i++){
h[i]=i;
}
for( int i=2;i*i<n;i++){
if(h[i]==i){
for(int j=i;j<n;j+=i){
h[j]=i;
}
}
}
return h;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int s,n;
cin>>s>>n;
vector<pair<int,pii>>v;
int dp[s+1]={0};
vector<pii>wei[s+1];
for(int i=0;i<n;i++){
int val,w,k;
cin>>val>>w>>k;
v.push_back({val,{w,k}});
wei[w].push_back({val,k});
}
vector<int>fw[s+1];
for(int i=1;i<=s;i++){
int num=((s+i-1)/i);
sort(all(wei[i]));
while(num>0&& wei[i].size()>0){
if(wei[i].back().second>0){
wei[i].back().second--;
fw[i].push_back(wei[i].back().first);
if(wei[i].back().second==0){
wei[i].pop_back();
}
num--;
}
}
}
for(int i=1;i<=s;i++){
for(auto c:fw[i]){
for(int j=s;j>=0;j--){
if(j-i<0)break;
if(j-i==0){
dp[j]=max(dp[j],c);
continue;
}
if(dp[j-i]>0){
dp[j]=max(dp[j],dp[j-i]+c);
}
}
}
}
int mx=*max_element(dp,dp+s+1);
cout<<mx<<endl;
return 0;
}
