#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Barang {
int v, w, k;
};
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int s, n; cin >> s >> n;
vector<Barang> bar(n);
for (auto &[v, w, k]: bar) {
cin >> v >> w >> k;
}
vector<Barang> nv;
for (auto &[v, w, k]: bar) {
int i = 1, tot = 0, kk = k;
while (k > 0 && tot + i <= kk) {
nv.push_back({v*i, w*i, i});
tot += i;
k -= i;
i++;
}
if (k > 0) nv.push_back({v*k, w*k, k});
}
vector<int> dp(s + 1);
dp[0] = 0;
for (auto &[v, w, k] : nv) {
for (int i=s; i>=w; --i) {
dp[i] = max(dp[i], dp[i-w] + v);
}
}
cout << dp[s];
}
