#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
typedef pair<ll, pair<ll, ll>> item;
void solve() {
ll x, n;
cin >> x >> n;
vector<item> items;
for (ll i = 0; i < n; i++) {
ll value, weight, amt;
cin >> value >> weight >> amt;
if (weight <= x && amt > 0) {
items.push_back({value, {weight, amt}});
}
}
sort(items.begin(), items.end(), [](const item &a, const item &b) {
if (a.first != b.first) return a.first > b.first;
return a.second.first < b.second.first;
});
n = items.size();
if (n == 0) {
cout << 0;
return;
}
if (n == 1) {
ll maxCopies = min(items[0].second.second, x / items[0].second.first);
cout << maxCopies * items[0].first;
return;
}
vector<item> new_item;
map<ll, ll> myMap;
for (item it: items) {
if (myMap[it.second.first] * it.second.first > x) continue;
myMap[it.second.first] += it.second.second;
new_item.push_back(it);
}
n = new_item.size();
vector<vector<ll>> dp(n + 1, vector<ll>(x + 1, 0));
for (ll i = n - 1; i >= 0; i--) {
for (ll j = 0; j <= x; j++) {
ll skip = dp[i + 1][j];
dp[i][j] = skip;
for (ll k = 1; k <= new_item[i].second.second && k*new_item[i].second.first<=j ; k++) {
if (j - k * new_item[i].second.first >= 0) {
ll pick = k * new_item[i].first + dp[i + 1][j - k * new_item[i].second.first];
dp[i][j] = max(dp[i][j], pick);
}
}
}
}
cout << dp[0][x];
}
int main() {
fast_io;
solve();
return 0;
}
