#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int W, n;
cin >> W >> n;
vector<array<long long, 2>> a; // { (value, weight) }
for (int i = 0; i < n; i++) {
long long v, w;
int cnt;
cin >> v >> w >> cnt;
int hbp = 31 - __builtin_clz(cnt);
for (int k = 0; k < hbp; k++) {
a.push_back({ v * (1 << k), w * (1 << k) });
}
cnt -= (1 << hbp) - 1;
for (int k = 0; k < 31; k++) {
if (cnt >> k & 1) {
a.push_back({ v * (1 << k), w * (1 << k) });
}
}
}
n = a.size();
vector<long long> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
for (int w = W; w >= a[i - 1][1]; w--) {
dp[w] = max( dp[w], dp[w - a[i - 1][1]] + a[i - 1][0] );
}
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
}
