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