#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cctype> #include <iomanip> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cstdlib> #include <bitset> #include <deque> #define inf 0x3f3f3f3f #define infll 0x3f3f3f3f3f3f3f3fll using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 100005; const int maxm = 2005; ll dp[maxm]; int n, m; ll c[maxn], v[maxn], w[maxn]; int main() { cin >> m >> n; for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i] >> c[i]; } for (int i = 1; i <= n; i++) { for (int j = m; j >= w[i]; j--) { for (int k = 1; k <= c[i] && k * w[i] <= j; k++) { dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]); } } } ll ans = 0; for (int i = 1; i <= m; i++) ans = max(ans, dp[i]); cout << ans << endl; return 0; }