#include<bits/stdc++.h>
#include <iostream>
typedef long long ll;
#define pb push_back
#define f first
#define s second
using namespace std;
ll dp[2001];
priority_queue<pair<ll,int>> kolejka[2001];
int n,max_weight;
void put(int waga){
auto x=kolejka[waga].top();
kolejka[waga].pop();
ll val=x.f; x.s--;
if(x.s)kolejka[waga].push(x);
if(kolejka[waga].top().s==0)kolejka[waga].pop();
for(int i=max_weight-waga;i>=0;i--)
dp[i+waga]=max(dp[i+waga],dp[i]+val);
for(int i=1;i<=max_weight;i++)dp[i]=max(dp[i],dp[i-1]);
}
int main()
{
cin>>max_weight>>n;
for(int i=0;i<n;i++){
ll v; int w,k;
cin>>v>>w>>k;
kolejka[w].push({v,k});
}
for(int i=1;i<=max_weight;i++){
for(int j=0;j<max_weight/i;j++){
if(kolejka[i].empty())break;
put(i);
}
}
cout<<dp[max_weight];
return 0;
}
