#include <bits/stdc++.h>
using namespace std;
// ---------- constants ----------
constexpr int MAX_S = 2000; // 1 ≤ S ≤ 2000
// ---------- helpers ----------
struct ItemType {
int v; // value (≤ 1 000 000)
int w; // weight (1 … S)
long long k; // copies (≤ 1e9)
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
if (!(cin >> S >> N)) return 0;
/* ---- 1. read & bucket by weight ---- */
vector<vector<pair<int,long long>>> bucket(S + 1); // bucket[w] = list of (value, copies)
for (int i = 0; i < N; ++i) {
ItemType it;
cin >> it.v >> it.w >> it.k;
if (it.w > S) continue; // too heavy, ignore
long long cap = S / it.w; // we never need more than this many copies
if (cap == 0) continue;
if (it.k > cap) it.k = cap;
bucket[it.w].push_back({it.v, it.k});
}
/* ---- 2. keep only the best S/w copies for each weight ---- */
struct Copy { int v, w; }; // one concrete copy
vector<Copy> copies;
copies.reserve(15200); // upper bound
for (int w = 1; w <= S; ++w) {
if (bucket[w].empty()) continue;
int lim = S / w; // maximum copies of weight w we can ever carry
auto &vec = bucket[w];
sort(vec.begin(), vec.end(), // sort by value descending
[](auto &a, auto &b) { return a.first > b.first; });
int taken = 0;
for (auto [v, k] : vec) {
if (taken == lim) break;
int cnt = static_cast<int>(min<long long>(k, lim - taken));
taken += cnt;
while (cnt--) copies.push_back({v, w}); // push each copy individually
}
}
/* ---- 3. 0/1 knapsack with at most 15 200 items ---- */
static int dp[MAX_S + 1]; // zero-initialised
for (const auto &cp : copies) {
int w = cp.w, v = cp.v;
for (int s = S; s >= w; --s)
dp[s] = max(dp[s], dp[s - w] + v);
}
cout << dp[S] << '\n';
return 0;
}
