#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"
#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);
int main() {
Algerian OI
ll s, n;
cin >> s >> n;
vector<ll> k(n), v(n), w(n);
for (ll i = 0; i < n; i++) {
cin >> v[i] >> w[i] >> k[i];
}
vector<ll> dp(s + 1, 0);
for (ll i = 0; i < n; i++) {
for (ll wt = s - 1; wt >= 0; wt--) {
for (ll amt = 1; amt <= k[i] && amt * w[i] + wt <= s; amt++) {
dp[wt + amt * w[i]] = max(dp[wt + amt * w[i]], dp[wt] + amt * v[i]);
}
}
}
ll res = 0;
for (ll i = 0; i <= s; i++) res = max(res, dp[i]);
cout << res << "\n";
return 0;
}
