using namespace std;
#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
// #include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long int> vll;
typedef pair<ll,ll> pll;
#define FOR(i,a,b) for(long long int i=a;i<b;i++)
#define all(v) v.begin(),v.end()
template <typename I>
void print(vector<I> &v){
FOR(i,0,v.size()-1){cout << v[i] << " ";}
cout << v.back() << "\n";
}
ll gcd(ll a,ll b){
if(a==0){return b;}
else if(b==0){return a;}
else if(a<b){return gcd(b%a,a);}
else{return gcd(a%b,b);}
}
ll lcm(ll a,ll b){
return (a/gcd(a,b))*b;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll s,n;
cin >> s >> n;
vll v(n);
vll w(n);
vll k(n);
FOR(i,0,n){
cin >> v[i] >> w[i] >> k[i];
}
vector<vector<pll>> weights(s+1);
FOR(i,0,n){
weights[w[i]].push_back({v[i],k[i]});
}
FOR(i,1,s+1){
if(!weights[i].empty()){
sort(all(weights[i]));
}
}
vll total(s+1,0);
FOR(i,1,s+1){
FOR(j,0,weights[i].size()){
total[i] += weights[i][j].second;
}
}
vll ans(s+1,-1);
ans[0] = 0;
FOR(i,1,s+1){
ll curr = weights[i].size()-1;
ll madhav = min(s/i,total[i]);
FOR(j,0,madhav){
if(weights[i][curr].second==0){
curr--;
}
for(ll m=s;m>=i;m--){
if(ans[m-i]!=-1){
ans[m] = max(ans[m],ans[m-i]+weights[i][curr].first);
}
}
weights[i][curr].second--;
}
}
cout << *max_element(all(ans)) << "\n";
return 0;
}
