#include<iostream>
#include<vector>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<set>
#include<math.h>
#include<map>
#include<deque>
#include<unordered_map>
#include<iomanip>
#include<queue>
#include<array>
#include<climits>
#include<cstring>
#include<unordered_set>
#include<cstdint>
#include<typeinfo>
using namespace std;
#define int long long
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int s,n;
cin>>s>>n;
map<int, vector<pair<int, int>>> m;
for(int i = 0; i<n; i++){
int x,y,z;
cin>>x>>y>>z;
if(y < s && z>0){
m[y].push_back({x,z});
}
}
vector<vector<long long>> v(m.size() + 1,vector<long long>(s + 1, INT32_MIN));
v[0][0] = 0;
int ind = 1;
for(auto &[x,z] : m){
sort(z.begin(), z.end(), greater<pair<int, int>>());
for (int i = 0; i <= s; i++) {
v[ind][i] = v[ind - 1][i];
int a = 0;
int b = 0;
int c = 0;
int d = 0;
while ((a + 1) * x <= i && b < z.size()) {
a++;
d += z[b].first;
if (v[ind - 1][i - a * x] != INT32_MIN) {
v[ind][i] = max(v[ind][i], v[ind - 1][i - a * x] + d);
}
c++;
if (c == z[b].second) {
c = 0;
b++;
}
}
}
ind ++;
}
cout<<*max_element(v.back().begin(), v.back().end());
}
