#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
void solve () {
ll s, n; cin >> s >> n;
map<ll, vector<pair<ll,ll>>> mp;
for (ll i = 0; i < n; i++) {
ll a, b, c; cin >> a >> b >> c;
if (b <= s and c > 0) {
mp[b].push_back({a, c});
}
}
vector<vector<ll>> dp(mp.size() + 1, vector<ll> (s + 1, -1e18));
dp[0][0] = 0;
ll pos = 1;
for (auto [x, y] : mp) {
sort(y.begin(), y.end(), greater<pair<ll,ll>>());
for (ll i = 0; i <= s; i++) {
dp[pos][i] = dp[pos - 1][i];
ll cnt = 0, j = 0, curr = 0, profit = 0;
while ((cnt + 1) * x <= i and j < y.size()) {
cnt++;
profit += y[j].first;
if (dp[pos - 1][i - cnt * x] != -1e18) {
dp[pos][i] = max(dp[pos][i], dp[pos - 1][i - cnt * x] + profit);
}
curr++;
if (curr == y[j].second) {
curr = 0;
j++;
}
}
}
pos++;
}
cout << *max_element(dp.back().begin(), dp.back().end());
}
int main() {
//freopen("filename.in", "r", stdin), freopen("filename.out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1; //cin >> t;
while (t--) solve();
}
