#include<bits/stdc++.h>
using namespace std;
#define dbg(a) cerr << #a << ": " << a << "\n"
using ll = long long;
void solve() {
ll s, n; cin >> s >> n;
vector<array<ll, 2>> a(n * 40);
int idx = 0;
for (int i = 0; i < n; ++i) {
ll v, w, k; cin >> v >> w >> k;
ll kk = 1;
while (k > 0) {
kk = min(kk, k);
if (kk * w > s) break;
a[idx++] = {kk * v, kk * w};
// a.push_back({kk * v, kk * w});
k -= kk;
kk *= 2;
}
}
a.resize(idx);
vector<ll> dp(s + 1);
for (auto [v, w]: a) {
for (ll i = s - w; i >= 0; --i) {
dp[i + w] = max(dp[i + w], dp[i] + v);
}
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int tc = 1;
for (int t = 1; t <= tc; ++t) {
solve();
}
}
