#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll s, n;
cin >> s >> n;
vector<ll> val(n + 1), w(n + 1), k(n + 1);
for (int i = 1; i <= n; i++) cin >> val[i] >> w[i] >> k[i];
vector<ll> dp(s + 1, 0);
for (ll i = 1; i <= n; i++) {
for (ll j = s; j >= w[i]; j--) {
for (ll cop = k[i]; cop >= 1; cop--) {
if (w[i] * cop > j) continue;
dp[j] = max(dp[j], dp[j - w[i] * cop] + val[i] * cop);
}
}
}
cout << dp[s] << "\n";
return 0;
}
