#ifdef LOCAL
#include ".debug.hpp"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
signed main() {
#ifndef VOID
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int N, S; cin >> S >> N;
vector<array<int, 3>> A(N); for (auto &a : A) cin >> a[0] >> a[1] >> a[2], a[2] = min(a[2], S);
vector<int64_t> dp(S + 1);
for (auto &[V, W, K] : A)
for (int k = 0; k < K; k++)
for (int j = S; j >= W; j--) dp[j] = max(dp[j], dp[j - W] + V);
cout << *max_element(dp.begin(), dp.end());
return 0;
}
