#include <bits/stdc++.h>
#include <cstdio>
#include <ios>
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define endl "\n"
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
using namespace std;
template<typename T> ostream& operator<<(ostream& out, vector<T>& a){for (auto &x: a) out << x << " "; out << endl; return out;}
const int mxN = 1e5+1, mxK = 21;
const long long MOD = 998244353;
long long modpow (long long a ,long long b) {long long res = 1;a %= MOD;while (b > 0) {if (b & 1) res = (res * a) % MOD;a = (a * a) % MOD;b >>= 1;}return res;}
long long modinv ( long long q ) {return modpow (q , MOD - 2);}
void solution() {
int S, N; cin >> S >> N;
vector<array<int, 3>> a(N); // (V, W, K)
FOR(i, 0, N) cin >> a[i][0] >> a[i][1] >> a[i][2];
vector<int> dp(S+1, 0);
FOR(i, 0, N){
ROF(w, 0, S+1){
FOR(k, 1, a[i][2]+1){
if (w - k*a[i][1] < 0) break;
dp[w] = max(dp[w], dp[w - k*a[i][1]]+k*a[i][0]);
}
}
}
int ans = 0;
FOR(i, 0, S+1) ans = max(ans, dp[i]);
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
freopen("in.txt", "r", stdin); freopen("snakes.out", "w", stdout);
solution();
return 0;
}
