#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }
using ll = long long;
using pii = std::pair<int, int>;
const int SMAX = 5e3;
const int NMAX = 1e5;
using namespace std;
vector<pair<int, int>> obj;
int dp[SMAX + 5], n, S;
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> S >> n;
for (int i = 1, v, w, k; i <= n; ++i) {
cin >> v >> w >> k;
k = min(k, (S / w) + 5);
int cnt = 1;
while (k > 0) {
int take = min(cnt, k);
obj.push_back({w * take, v * take});
k -= take;
cnt <<= 1;
}
}
fill(dp + 1, dp + S + 1, INT_MIN);
dp[0] = 0;
for (auto &[w, v] : obj) {
if (w > S) continue;
for (int i = S; i >= w; --i)
dp[i] = max(dp[i], dp[i - w] + v);
}
cout << *max_element(dp, dp + S + 1) << '\n';
return 0;
}
