#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
typedef long double ld;
#define int ll
using pi = array<ll, 2>;
const int MOD = 1e9+7;
struct DSU{
private:
vector<int> parents, sizes;
public:
void init(int n){
parents.resize(n); iota(parents.begin(), parents.end(), 0);
sizes.resize(n, 1);
}
int find(int x){return parents[x]==x?x:(parents[x]=find(parents[x]));}
bool unite(int a, int b){
int root_a = find(a);
int root_b = find(b);
if(root_a==root_b) return false;
if(sizes[root_a]<sizes[root_b]) swap(root_a, root_b);
sizes[root_a] += sizes[root_b];
parents[root_b] = root_a;
return true;
}
};
// max sum robime
class SegTree{
private:
struct item{
int pref = 0;
int suff = 0;
int sum = 0;
int most = 0;
};
int n;
vector<item> values;
item merge(item a, item b){
int pref = max(a.pref, a.sum+b.pref);
int suff = max(b.suff, b.sum+a.suff);
int sum = a.sum+b.sum;
int most = max({a.most, b.most, a.suff+b.pref});
return {pref, suff, sum, most};
}
item solo(int v){
if(v>0){
return {v,v,v,v};
}
return {0,0,v,0};
}
void pset(int idx, int v){
values[idx+=n] = solo(v);
for(idx/=2; idx > 0; idx>>=1)
values[idx] = merge(values[2*idx], values[2*idx+1]);
}
item pget(int l, int r){
item right, left;
for(l+=n, r+=n; l<r; l>>=1, r>>=1){
if (l & 1) left = merge(left, values[l++]);
if (r & 1) right = merge(values[--r], right);
}
return merge(left, right);
}
public:
void init(int n){
this->n = n;
values.resize(2*n);
}
void set(int idx, int v){
pset(idx, v);
}
int get(int l, int r){
return pget(l, r).most;
}
};
int lis(vector<int> a){
vector<int> arr;
for(int i = 0; i < a.size(); ++i){
int pos = upper_bound(arr.begin(), arr.end(), a[i]) - arr.begin();
if(pos==arr.size()){
arr.push_back(a[i]);
}else{
arr[pos] = a[i];
}
}
return arr.size();
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int limit, number;
cin >> limit >> number;
map<int, vector<pair<int,int>>> by_weight;
for (int t = 0; t < number; t++) {
int value;
int weight;
int amt;
cin >> value >> weight >> amt;
if (weight <= limit && amt > 0) { by_weight[weight].push_back({value, amt}); }
}
vector<vector<int>> best(by_weight.size() + 1, vector<int>(limit + 1, INT32_MIN));
best[0][0] = 0;
int at = 1;
for(auto &[w, items] : by_weight) {
sort(items.rbegin(), items.rend());
for (int i = 0; i <= limit; i++) {
best[at][i] = best[at - 1][i];
int copies = 0;
int type_at = 0;
int curr_used = 0;
int profit = 0;
while ((copies + 1) * w <= i && type_at < items.size()) {
copies++;
profit += items[type_at].first;
if(best[at - 1][i - copies * w] != INT32_MIN) {
best[at][i] =
max(best[at][i], best[at - 1][i - copies * w] + profit);
}
curr_used++;
if (curr_used == items[type_at].second) {
curr_used = 0;
type_at++;
}
}
}
at++;
}
cout << *max_element(best.back().begin(), best.back().end()) << '\n';
return 0;
}
