#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
ll S, n;
cin >> S >> n;
vector<ll> V(n+1), W(n+1), K(n+1);
for (ll i = 1; i <= n; i++) {
cin >> V[i] >> W[i] >> K[i];
K[i] = min(K[i], 2000LL);
}
vector<vector<ll>> dp(n+1, vector<ll>(S+1, 0));
for (ll i = 1; i <= n; i++) {
for (ll w = 1; w <= S; w++) {
for (ll j = 0; j <= K[i]; j++) {
if (w - j*W[i] < 0) break;
dp[i][w] = max(dp[i][w], dp[i-1][w-j*W[i]] + j*V[i]);
}
}
}
// for (ll i = 0; i <= n; i++) {
// for (ll w = 0; w <= S; w++) {
// cout << dp[i][w] << ' ';
// }
// cout << '\n';
// }
cout << *max_element(dp[n].begin(), dp[n].end()) << '\n';
}
int main() {
// freopen("cowmbat.in", "r", stdin);
// freopen("cowmbat.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
