#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define pb push_back
using ll = long long;
const int MAXK = 2005; // max weight capacity
int main() {
fastio
int k, n;
cin >> k >> n;
vector<int> value(n+1), weight(n+1), freq(n+1);
for (int i = 1; i <= n; i++) {
cin >> value[i] >> weight[i] >> freq[i];
}
// Use binary decomposition to convert bounded knapsack to 0/1 knapsack
vector<int> new_weight, new_value;
for (int i = 1; i <= n; i++) {
int f = freq[i], w = weight[i], v = value[i];
for (int j = 1; f > 0; j <<= 1) {
int cnt = min(j, f);
new_weight.pb(cnt * w);
new_value.pb(cnt * v);
f -= cnt;
}
}
// Now apply 0/1 knapsack DP on new_weight/new_value
vector<int> dp(k + 1, 0);
for (int i = 0; i < new_weight.size(); i++) {
for (int j = k; j >= new_weight[i]; j--) {
dp[j] = max(dp[j], dp[j - new_weight[i]] + new_value[i]);
}
}
cout << dp[k] << endl;
return 0;
}
