#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T,null_type,less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define f(i,a,b) for(int i=int (a);i<=int (b);i++)
#define ff(i,a,b) for(int i=int (a);i<int (b);i++)
#define F(i,a,b) for(int i=int (a);i>=int (b);i--)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define lower(p,x) lower_bound(all(p),x)
#define upper(p,x) upper_bound(all(p),x)
#define ms(a,x) memset(a,x,sizeof (a))
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const double eps=1e-9,pi=acos(-1.0);
const int N=1e6+6,inf=0x3f3f3f3f,mod=1e9+7;
int main()
{
int s,n;
cin>>s>>n;
map<int,vector<pair<int,int>>> by_weight;
ff(i,0,n)
{
int v,w,k;
cin>>v>>w>>k;
by_weight[w].pb({v,k});
}
vector<vector<ll>> b(by_weight.size()+1,vector<ll>(s+1,INT32_MIN));
b[0][0]=0;
int att=1;
for(auto &[w,items]: by_weight){
sort(items.begin(),items.end(),greater<pair<int,int>>());
for(int i=0;i<=s;i++){
b[att][i]=b[att-1][i];
int copies=0;
int type_att=0;
ll value=0;
int cur_used=0;
while((copies+1)*w<=i&&type_att<items.size()){
copies++;
value+=items[type_att].fi;
if(b[att-1][i-copies*w]!=INT32_MIN)
b[att][i]=max(b[att][i],b[att-1][i-copies*w]+value);
cur_used++;
if(cur_used==items[type_att].se){
type_att++;
cur_used=0;
}
}
}
att++;
}
cout<<*max_element(b.back().begin(),b.back().end());
}
