#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
if (!(cin >> S >> N)) return 0;
// buckets by weight: for weight w, store vector of pairs (value, count)
vector<vector<pair<int, long long>>> bucket(S + 1);
for (int i = 0; i < N; ++i) {
int V, W; long long K;
cin >> V >> W >> K; // Vi Wi Ki
if (W > S) continue; // theo đề W <= S nhưng an toàn
bucket[W].push_back({V, K});
}
// build list of unit-items after truncation by t_w = floor(S / w)
struct Item { int w; int v; };
vector<Item> items;
items.reserve(S * 12); // ước lượng (S log S)
for (int w = 1; w <= S; ++w) {
if (bucket[w].empty()) continue;
// sort types of this weight by value descending
auto &vec = bucket[w];
sort(vec.begin(), vec.end(), [](const auto &a, const auto &b){
return a.first > b.first;
});
int need = S / w; // at most this many copies of weight w can be used
for (auto &p : vec) {
if (need <= 0) break;
int val = p.first;
long long cnt = p.second;
long long take = min<long long>(cnt, need);
// push `take` unit items (value = val, weight = w)
for (long long t = 0; t < take; ++t) items.push_back({w, val});
need -= (int)take;
}
}
// 0/1 knapsack DP on items
vector<ll> dp(S + 1, 0);
for (auto &it : items) {
int w = it.w, v = it.v;
for (int j = S; j >= w; --j) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[S] << '\n';
return 0;
}
