#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <array>
#include <set>
#include <climits>
#include <map>
#include <memory>
#include <string>
#include <deque>
#include <queue>
#include <stack>
using namespace std;
#define input "knapsack.in"
#define output "knapsack.out"
#define int long long
typedef pair<int, int> pii;
int S, n;
vector<vector<pii>> items;//grouped by weight
vector<pii> all_items;//each weight can have up to S pounds in this vector, making it SlogS
vector<int> dp;//for each weight, what is the maximum value possible?
int res=0;
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen(input, "r", stdin);
//freopen(output, "w", stdout);
cin >> S >> n;
items.resize(S+1);
dp.resize(S+1, 0);
for (int i=0;i<n;i++) {
int val, wt, amt;
cin >> val >> wt >> amt;
items[wt].push_back({val, amt});
}
for (int s=1;s<=S;s++) {
sort(items[s].begin(), items[s].end(), [](pii& a, pii& b) -> bool {
return a.first>b.first;
});
}
all_items.reserve(S*S);
for (int s=1;s<=S;s++) {
int curr_weight=0;
for (pii item: items[s]) {
for (int k=0;k<item.second;k++) {
curr_weight+=s;
if (curr_weight>S) break;
all_items.push_back({s, item.first});
}
if (curr_weight>S) break;
}
}
for (pii item: all_items) {
//out << item.first << ' ' << item.second << endl;
for (int s=S-1;s>=0;s--) {
if (item.first+s>S) continue;
dp[item.first+s]=max(dp[item.first+s], item.second+dp[s]);
res=max(res, dp[item.first+s]);
}
}
//for (int s=0;s<=S;s++) cout << dp[s] << ' '; cout << endl;
//cout << all_items.size() << endl;
cout << res << endl;
}
