#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to solve the bounded knapsack problem
int knapsack(int S, int N, vector<tuple<int, int, int>>& items) {
// dp[w] will store the max value we can achieve with weight w
vector<int> dp(S + 1, 0);
// Process each item (V: value, W: weight, K: quantity)
for (const auto& item : items) {
int V, W, K;
tie(V, W, K) = item;
int count = 1;
while (K > 0) {
int current_count = min(count, K);
K -= current_count;
int item_weight = current_count * W;
int item_value = current_count * V;
// Update dp array using 0/1 knapsack for this batch of items
for (int weight = S; weight >= item_weight; --weight) {
dp[weight] = max(dp[weight], dp[weight - item_weight] + item_value);
}
count *= 2;
}
}
// The maximum value we can achieve with total weight <= S
return *max_element(dp.begin(), dp.end());
}
int main() {
int S, N;
// Read S (maximum weight) and N (number of item types)
cin >> S >> N;
// Store the items as tuples (value, weight, quantity)
vector<tuple<int, int, int>> items(N);
for (int i = 0; i < N; ++i) {
int V, W, K;
cin >> V >> W >> K;
items[i] = make_tuple(V, W, K);
}
// Solve the problem
cout << knapsack(S, N, items) << endl;
return 0;
}
