#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
signed main() {
cin.tie(nullptr); cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int s, n;
cin >> s >> n;
int v[n], w[n], k[n];
for (int i = 0; i < n; i++) {
cin >> v[i] >> w[i] >> k[i];
}
int dp[n+1][s+1];
for (int i = 1; i <= s; i++) {
dp[0][i] = 0;
}
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= s; j++) {
dp[i][j] = dp[i-1][j];
int imti = min(j/w[i-1], k[i-1]);
imti = min(imti, (int)1);
dp[i][j] = max(dp[i][j], dp[i-1][j-(imti*w[i-1])]+(imti*v[i-1]));
ans = max(dp[i][j], ans);
}
}
cout << ans << endl;
cout.flush();
return 0;
}
