#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Item {
int value, weight, copies;
// Default constructor
Item() {
value = 0;
weight = 0;
copies = 0;
}
Item(int value, int weight, int copies) {
this->value = value;
this->weight = weight;
this->copies = copies;
}
};
int knapsack(int S, int N, Item arr[]) {
vector<vector<int>> dp(N + 1, vector<int>(S + 1, 0));
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= S; j++) {
dp[i][j] = dp[i - 1][j]; // Initialize with the previous row's value
// Consider multiple copies of the same item
for (int k = 1; k <= arr[i - 1].copies && k * arr[i - 1].weight <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * arr[i - 1].weight] + k * arr[i - 1].value);
}
}
}
return dp[N][S];
}
int main() {
int S, N;
cin >> S >> N;
Item arr[N];
for (int i = 0; i < N; i++) {
int value, weight, copies;
cin >> value >> weight >> copies;
arr[i] = Item(value, weight, copies); // Initialize the Item array
}
int result = knapsack(S, N, arr);
cout << result << endl; // Print the maximum total value
return 0;
}
