#include<iostream>
#include<string>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#include<vector>
#include <map>
#define pii pair<int, int>
using namespace std;
int mod = 1000000007;
int s, n;
const int N = 100001;
vector<long long> c(N, 0);
vector<long long> w(N, 0);
vector<long long> q(N, 0);
long long solve() {
//if we group the items by weights we know we can have at most 2000 different
//items, with the sum of same weights as the freq and varying costs for each
//we should also take the item with the highest cost from a group
map<int, vector<pii>> weight_map;
for (int i=1; i<=n; i++) weight_map[w[i]].push_back({c[i], q[i]});
for (auto& tp: weight_map) sort(tp.second.begin(), tp.second.end(), greater<pii>());
vector<long long> dp(s+1, -1);
long long ans = 0;
dp[0] = 0;
for (auto const& [weight, data]: weight_map) {
for (int j=s; j>=0; j--) {
long long cnt = 0;
long long cost = 0;
for (pii d: data) {
if (cnt > j/weight) break;
for (int k=0; k<d.second; k++) {
cnt++;
if (j - cnt*weight < 0) break;
cost += d.first;
if (dp[j-cnt*weight] == -1) continue;
dp[j] = max(dp[j], dp[j-cnt*weight] + cost);
}
}
ans = max(ans, dp[j]);
}
}
return ans;
}
int main() {
cin >> s >> n;
for (int i=1; i<=n; i++) cin >> c[i] >> w[i] >> q[i];
cout << solve() << "\n";
}
