#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ft first
#define sd second
using namespace std;
using namespace __gnu_pbds;
using bs = bitset<8000>;
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int M = 2005;
ll dp[M];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll w, n; cin >> w >> n;
vector<pll> it;
for (int i = 0; i < n; ++i) {
ll v, wt, k; cin >> v >> wt >> k;
for (ll j = 1; j <= k; j <<= 1) {
if (wt * j > w) break;
it.push_back({v * j, wt * j});
k -= j;
}
if (k && wt * k <= w) it.push_back({v * k, wt * k});
}
for (auto &p: it) {
for (ll j = w; j >= p.sd; --j)
dp[j] = max(dp[j], dp[j - p.sd] + p.ft);
}
cout << dp[w] << '\n';
return 0;
}
