#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];
}
vll dp(S + 1);
dp[0] = 0;
rep(numC, 1, k[0] + 1) {
if (numC * w[0] > S) {
break;
}
dp[numC * w[0]] = numC * v[0];
}
rep(i, 1, S + 1) upmax(dp[i], dp[i - 1]);
rep(i, 1, n) {
vll nextdp(S + 1);
nextdp[0] = 0;
rep(j, 1, S + 1) {
rep(numC, 0, k[i] + 1) {
if (j - numC * w[i] < 0) {
break;
}
upmax(nextdp[j], dp[j - numC * w[i]] + numC * v[i]);
}
}
swap(dp, nextdp);
}
/*
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[S] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
