#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef long double ld;
#define sz(s) ((int)s.size())
#define all(v) begin(v), end(v)
#define ff first
#define ss second
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
// *-> KISS*
int solve() {
ll s, n; cin >> s >> n;
vector<array<ll, 3>> v(n); // value, weight, number
for (int i = 0; i < n; i++) {
cin >> v[i][0] >> v[i][1] >> v[i][2];
}
vector<vector<ll>> dp(2, vector<ll>(s + 1, 0));
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= s; ++j) {
dp[i % 2][j] = dp[(i - 1) % 2][j];
for(int k = 0; k <= v[i - 1][2]; ++k) {
ll ex = v[i - 1][0] * k, wi = v[i - 1][1] * k;
if(wi > j) break;
dp[i % 2][j] = max(dp[i % 2][j], ex + dp[(i - 1) % 2][j - wi]);
}
}
}
cout << dp[n % 2][s];
return 0;
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
bool test = false;
int TET = 1;
if(test) cin >> TET;
cout << fixed << setprecision(6);
for (int i = 1; i <= TET; i++) {
#ifdef LOCAL
cout << "##################" << '\n';
#endif
if (solve()) {
break;
}
cout << '\n';
}
#ifdef LOCAL
cout << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
return 0;
}
// -> Keep It Simple Stupid!
