#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
const ll DIM = 1e6 + 7;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll maxlog = 20;
const ll bsize = 350;
ll dp[107][2007];
void solve() {
ll s, n;
cin >> s >> n;
for (int i=1; i<=n; i++) {
ll val, w, k;
cin >> val >> w >> k;
for (int nw=1; nw<=s; nw++) {
for (int j=0; j<=min(k, s); j++) {
if (nw < w*j) break;
dp[i][nw] = max(dp[i][nw], dp[i-1][nw-w*j] + val*j);
}
}
//for (int nw=0; nw<=s; nw++) cout << dp[i][nw] << " ";
//cout << endl;
}
ll ans = 0;
for (int i=s; i>=0; i--) {
ans = max(ans, dp[n][i]);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int ntest = 1;
//cin >> ntest;
while (ntest--) {
solve();
}
return 0;
}
;
