#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
ll S, N; cin >> S >> N;
vector<tuple<ll, ll, ll>> items(N+1);
for (int i = 1; i <= N; i++) {
ll v,w,k; cin >> v >> w >> k;
items[i] = make_tuple(v,w,k);
}
vector<vector<ll>> dp(N+1, vector<ll>(S+1, 0));
for (ll i = 1; i <= N; i++) {
for (ll j = 0; j <= get<2>(items[i]); j++) {
for (ll z = 0; z <= S; z++) {
ll newWeight = z + get<1>(items[i]) * j;
if (newWeight <= S) {
dp[i][newWeight] = max(dp[i][newWeight], dp[i-1][z] + get<0>(items[i]) * j);
} else {break;}
}
}
}
ll ans{0};
for (ll i = 0; i <= S; i++) {
ans = max(ans, dp[N][i]);
}
cout << ans << endl;
return 0;
}
