#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
ll solve(vector<ll> v, vector<ll> w, ll S, ll n) {
ll dp[n + 1][S + 1];
for (int i = 0; i <= S; i++) {
dp[0][i] = 0;
}
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= S; j++) {
if (j - w[i] >= 0) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][S];
}
int main() {
ll S, N;
cin >> S >> N;
vector<ll> v(1), w(1), k(N); // index 0 dummy, like you used
for (int i = 0; i < N; ++i) {
ll val, wei, cnt;
cin >> val >> wei >> cnt;
k[i] = cnt;
// Binary Decomposition for bounded knapsack
for (ll j = 1; cnt > 0; j <<= 1) {
ll take = min(j, cnt);
v.push_back(val * take);
w.push_back(wei * take);
cnt -= take;
}
}
ll newN = v.size() - 1;
ll ans = solve(v, w, S, newN);
cout << ans << endl;
return 0;
}
