#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
int s, n;
cin >> s >> n;
vector<vector<int> > v(n, vector<int>(3)); // Stores {value, weight, max_quantity}
for (int i = 0; i < n; i++) {
int value, weight, max_quantity;
cin >> value >> weight >> max_quantity;
v[i][0] = value; // Store value
v[i][1] = weight; // Store weight
v[i][2] = max_quantity; // Store max_quantity
}
vector<vector<int> > dp(n + 1, vector<int>(s + 1, 0)); // DP table
for (int i = n - 1; i >= 0; i--) { // Iterate over items
for (int j = 0; j <= s; j++) { // Iterate over possible capacities
dp[i][j] = dp[i + 1][j]; // Case: Don't take the item
for (int k = 1; k <= v[i][2]; k++) { // Consider all quantities up to max_quantity
int weight = k * v[i][1];
if (j >= weight) {
dp[i][j] = max(dp[i][j], k * v[i][0] + dp[i + 1][j - weight]);
}
}
}
}
cout << dp[0][s] << endl; // Maximum value achievable with total capacity `s`
}
