#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_S = 2000; // given in the statement
static int dp[MAX_S + 1]; // zero-initialised by the loader
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
if (!(cin >> S >> N)) return 0;
vector<int> V(N), W(N);
vector<long long> K(N); // the count can be up to 1e9, keep as 64-bit
for (int i = 0; i < N; ++i) {
cin >> V[i] >> W[i] >> K[i];
if (W[i] != 0) K[i] = min<long long>(K[i], S / W[i]); // never need more
}
/* ---- main loop ---- */
for (int idx = 0; idx < N; ++idx) {
int v = V[idx], w = W[idx];
long long k = K[idx];
for (long long p = 1; k > 0; p <<= 1) {
int take = static_cast<int>(min<long long>(p, k));
int wt = w * take; // ≤ 2 000 × 2 048 = 4 096 000 < 2^31
int val = v * take; // ≤ 1 024 × 1 000 000 = 1 024 000 000
/* 0/1 knapsack update */
for (int s = S; s >= wt; --s)
dp[s] = max(dp[s], dp[s - wt] + val);
k -= take;
}
}
cout << dp[S] << '\n';
return 0;
}
