#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast_io \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
signed main() {
fast_io;
int s, n;
cin >> s >> n;
vector<array<int, 3>> v(n);
for (auto& i : v) cin >> i[0] >> i[1] >> i[2];
vector<vector<array<int, 2>>> bywt(s + 1);
for (auto i : v) bywt[i[1]].push_back({i[0], i[2]});
for (auto& i : bywt) sort(i.begin(), i.end(), greater<>());
vector<array<int, 2>> items;
for (int wt = 1; wt <= s; wt++) {
int take = s / wt;
for (auto i : bywt[wt]) {
int cnt = min(take, i[1]);
for (int j = 0; j < cnt; j++) items.push_back({i[0], wt});
take -= cnt;
if (take == 0) break;
}
}
vector<int> dp(s + 1);
for (int i = 0; i < (int)items.size(); i++) {
for (int wt = s; wt >= items[i][1]; wt--) {
dp[wt] = max(dp[wt], dp[wt - items[i][1]] + items[i][0]);
}
}
cout << dp[s] << "\n";
return 0;
}
