#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> intpair;
typedef pair<ll, ll> llpair;
// const int MOD = 1e9 + 7;
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int maxWeight, typeCnt; cin >> maxWeight >> typeCnt;
map<int, vector<intpair>> byWeight;
for (int t = 0; t < typeCnt; t++) {
int value, weight, amt; cin >> value >> weight >> amt;
if (weight <= maxWeight && amt > 0) {
byWeight[weight].push_back({value, amt});
}
}
vector<vector<ll>> dp(byWeight.size() + 1, vector<ll>(maxWeight + 1, INT32_MIN));
dp[0][0] = 0;
int at = 1;
for (auto &[w, items] : byWeight) {
sort(items.begin(), items.end(), greater<intpair>());
for (int i = 0; i <= maxWeight; i++) {
dp[at][i] = dp[at - 1][i];
int copies = 0;
int typeAt = 0;
int currUsed = 0;
ll profit = 0;
while ((copies + 1) * w <= i && typeAt < items.size()) {
copies++;
profit += items[typeAt].first;
if (dp[at - 1][i - copies * w] != INT32_MIN) {
dp[at][i] = max(dp[at][i], dp[at - 1][i - copies * w] + profit);
}
currUsed++;
if (currUsed == items[typeAt].second) {
currUsed = 0;
typeAt++;
}
}
}
at++;
}
cout << *max_element(dp.back().begin(), dp.back().end()) << endl;
}
int main() {
solve();
return 0;
}
