#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(v) v.begin(), v.end()
using namespace std;
using pii = pair<int, int>;
int s, n, m;
vector<pii> a; // {value, weight}
vector<int> dp;
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> s >> n;
while (n--) {
int v, w, k;
cin >> v >> w >> k;
int x = 1;
while (x <= k) {
if (w * x <= s) a.push_back({v * x, w * x});
k -= x;
x <<= 1;
}
a.push_back({v * k, w * k});
}
m = a.size(); a.insert(a.begin(), {0, 0});
dp.assign(s + 1, 0);
for (int i = 1; i <= m; ++i) {
for (int j = s; j >= a[i].se; --j) {
dp[j] = max(dp[j], dp[j - a[i].se] + a[i].fi);
}
}
cout << dp[s];
}
