#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using vi = vector<int>; #define all(x) (x).begin(), (x).end() ll dp[2001]; int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); int s, n; cin >> s >> n; vector<ll> v, w; ll x, y, z; for (int i = 0; i < n; ++i) { cin >> x >> y >> z; ll c = 1; while (c < z) { v.push_back(x * c); w.push_back(y * c); z -= c; c *= 2; } if (z > 0) { v.push_back(x * z); w.push_back(y * z); } } for (int i = 0; i < v.size(); ++i) { for (int j = s; j >= w[i]; --j) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[s] << '\n'; return 0; }