#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Item { int v, w, k; }; int s, n; Item store[100'000]; ll dp[2001]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> s >> n; for (int i = 0; i < n; ++i) { cin >> store[i].v >> store[i].w >> store[i].k; } for (int i = 0; i < n; ++i) { for (int w = s; w >= 0; --w) { for (int multiplicity = 0; multiplicity <= store[i].k; ++multiplicity) { if (w - multiplicity * store[i].w < 0) break; dp[w] = max(dp[w], dp[w - multiplicity * store[i].w] + multiplicity * store[i].v); } } } cout << dp[s] << '\n'; return 0; }