#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Barang {
int v, w, k;
};
struct Nb {
int v, w;
};
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<Nb> nv;
for (auto &[v, w, k]: bar) {
int i=1;
while (k > 0) {
int now = min(i, k);
nv.push_back({v * now, w * now});
k -= now;
i <<= 1;
}
}
vector<int> dp(s + 1);
dp[0] = 0;
for (auto &[v, w] : nv) {
for (int i=s; i>=w; --i) {
dp[i] = max(dp[i], dp[i-w] + v);
}
}
cout << dp[s];
}
