#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// Read the maximum capacity S and number of item types N
int S, N;
cin >> S >> N;
// Input arrays
vector<int> values(N); // Vi: value of item i
vector<int> weights(N); // Wi: weight of item i
vector<int> counts(N); // Ki: number of copies of item i available
// Read item information
for (int i = 0; i < N; i++) {
cin >> values[i] >> weights[i] >> counts[i];
}
// Create a DP table where dp[w] represents the maximum value achievable with a weight capacity of w
vector<int> dp(S + 1, 0);
// For each item type
for (int i = 0; i < N; i++) {
// Process each item using the binary optimization technique
// We'll convert K copies into powers of 2 + a remaining item
int value = values[i];
int weight = weights[i];
int count = counts[i];
// Create "binary" copies of the item to handle efficiently
vector<pair<int, int>> binary_items;
// Express count in binary representation (1, 2, 4, 8, etc.)
for (int k = 1; count > 0; k *= 2) {
int take = min(k, count);
if (take > 0) {
binary_items.push_back({take * value, take * weight});
}
count -= take;
}
// Apply 0/1 knapsack for each binary item
for (auto& item : binary_items) {
int item_value = item.first;
int item_weight = item.second;
// Update the DP table from right to left to avoid counting the same item multiple times
for (int w = S; w >= item_weight; w--) {
dp[w] = max(dp[w], dp[w - item_weight] + item_value);
}
}
}
// The answer is in dp[S]
cout << dp[S] << endl;
return 0;
}
