#pragma GCC optimize("O3,inline,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).begin(), (v).end()
#define debug cerr << "[DEBUG] "
const char wp = ' ';
const char nl = '\n';
void kebin() {
ll s, n;
cin >> s >> n;
vector<tuple<ll, ll, ll>> arr(n);
for (auto &[a, b, c] : arr) {
cin >> a >> b >> c;
}
vector<pair<ll, ll>> items;
vector<ll> dp(s+1);
for (auto [val, w, cnt] : arr) {
ll k = 1;
while (cnt > 0) {
ll tmp = min(cnt, k);
items.push_back({val * tmp, w * tmp});
cnt -= tmp;
k <<= 1;
}
}
for (auto [val, weight] : items) {
for (int w = s; w >= weight; w--) {
dp[w] = max(dp[w], dp[w - weight] + val);
}
}
cout << *max_element(all(dp)) << nl;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--) kebin();
}
