#include <bits/stdc++.h>
#ifdef LOCAL
#include <windows.h>
#endif
using namespace std;
#ifdef LOCAL
template<typename T>
void debugPrint(int line, const string& varName, const T& value) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 10);
cerr << "Line " << line << ": " << varName << " = " << value << "\n";
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}
#define dbg(x) debugPrint(__LINE__, #x, x)
#endif
#define TestCases int TC; cin >> TC; while (TC--)
template <class Fun> class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
template <class... Args> decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun> decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
struct AUTOIOS {
AUTOIOS() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
} autoios;
constexpr int modulo = 1e9 + 7;
mt19937 mt(static_cast<unsigned>(time(nullptr)));
uniform_int_distribution<int> range(0, 2);
template<typename T>
struct CMP {
bool operator() (const T &a, const T &b) const {
return a < b;
}
};
int main() {
int s, n;
cin >> s >> n;
vector<vector<pair<int, int>>> weight(s + 1);
for (int i = 1, v, w, k; i <= n; i++) {
cin >> v >> w >> k;
if (w > s) continue;
weight[w].push_back({v, k});
}
vector<int> dp(s + 1);
for (int w = 1; w <= s; w++) {
sort(weight[w].begin(), weight[w].end(), greater<pair<int, int>>());
// 挑选 weight = w 重量时，前 s / w 个 value 最高的物品
int num = s / w;
for (auto it : weight[w]) {
// 对于 weight = w 物品时，至多选择 take 个物品(二进制优化法)
auto [v, k] = it; int take = min(k, num); num -= take;
for (int b = 1, bv, bw; b <= take; take -= b, b *= 2) {
bv = b * v;
bw = b * w;
if (bw > s) break;
for (int i = s; i >= bw; i--) {
dp[i] = max(dp[i], dp[i - bw] + bv);
}
}
if (take && take * w <= s) for (int i = s; i >= take * w; i--) {
dp[i] = max(dp[i], dp[i - take * w] + take * v);
}
if (num == 0) break;
}
}
cout << dp[s];
return 0;
}
