#include <iostream>
#include <vector>
#include <algorithm>
int knapsack(int S, const std::vector<std::tuple<int, int, int>>& items) {
std::vector<int> dp(S + 1, 0);
for (const auto& [value, weight, count] : items) {
int k = count;
int mul = 1;
while (k > 0) {
int take = std::min(mul, k);
int total_value = take * value;
int total_weight = take * weight;
for (int j = S; j >= total_weight; --j) {
dp[j] = std::max(dp[j], dp[j - total_weight] + total_value);
}
k -= take;
mul <<= 1; // multiply by 2
}
}
return *std::max_element(dp.begin(), dp.end());
}
int main() {
int S, N;
std::cin >> S >> N;
std::vector<std::tuple<int, int, int>> items(N);
for (int i = 0; i < N; ++i) {
int v, w, k;
std::cin >> v >> w >> k;
items[i] = {v, w, k};
}
std::cout << knapsack(S, items) << '\n';
return 0;
}
