#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
void solve() {
ll n, S;
cin >> S >> n;
vll v(n), w(n), k(n);
rep(i, 0, n) {
cin >> v[i] >> w[i] >> k[i];
}
vvll dp(n, vll(S + 1));
rep(i, 0, n) dp[i][0] = 0;
rep(numC, 1, k[0] + 1) {
if (numC * w[0] > S) {
break;
}
dp[0][numC * w[0]] = numC * v[0];
}
rep(i, 1, S + 1) upmax(dp[0][i], dp[0][i - 1]);
rep(i, 1, n) {
rep(j, 1, S + 1) {
rep(numC, 0, k[i] + 1) {
if (j - numC * w[i] < 0) {
break;
}
upmax(dp[i][j], dp[i - 1][j - numC * w[i]] + numC * v[i]);
}
}
}
cout << dp[n - 1][S] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
