#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int value;
int weight;
long long quantity;
};
long long knapsack_single_item(int S, const Item& item) {
return static_cast<long long>(item.value) * min(item.quantity, static_cast<long long>(S / item.weight));
}
long long knapsack_01(int S, const vector<Item>& items) {
vector<long long> dp(S + 1, 0);
for (const auto& item : items) {
for (int s = S; s >= item.weight; s--) {
dp[s] = max(dp[s], dp[s - item.weight] + item.value);
}
}
return dp[S];
}
long long knapsack_bounded(int S, const vector<Item>& items) {
vector<long long> dp(S + 1, 0);
for (const auto& item : items) {
for (int s = S; s >= item.weight; s--) {
for (int count = 1; count <= min(item.quantity, static_cast<long long>((s / item.weight))); count++) {
dp[s] = max(dp[s], dp[s - count * item.weight] + count * static_cast<long long>(item.value));
}
}
}
return dp[S];
}
long long knapsack_large_quantities(int S, const vector<Item>& items) {
vector<long long> dp(S + 1, 0);
for (const auto& item : items) {
if (item.value == 0 || item.weight == 0 || item.weight > S) {
continue;
}
vector<pair<long long, int>> binary_items;
long long remaining = item.quantity;
long long q = 1;
while (remaining > 0) {
if (remaining & 1) {
long long package_value = static_cast<long long>(item.value) * q;
int package_weight = item.weight * q;
if (package_weight <= S) {
binary_items.push_back({package_value, package_weight});
}
}
q *= 2;
remaining >>= 1;
if (item.weight * q > S) {
break;
}
}
for (const auto& [package_value, package_weight] : binary_items) {
for (int s = S; s >= package_weight; s--) {
dp[s] = max(dp[s], dp[s - package_weight] + package_value);
}
}
}
return dp[S];
}
long long solve_knapsack(int S, const vector<Item>& items) {
int N = items.size();
if (N == 1) {
return knapsack_single_item(S, items[0]);
}
bool all_quantity_one = true;
for (const auto& item : items) {
if (item.quantity != 1) {
all_quantity_one = false;
break;
}
}
if (all_quantity_one) {
return knapsack_01(S, items);
}
bool all_small_quantities = true;
for (const auto& item : items) {
if (item.quantity > 10) {
all_small_quantities = false;
break;
}
}
if (N <= 100 && all_small_quantities) {
return knapsack_bounded(S, items);
}
return knapsack_large_quantities(S, items);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int S, N;
cin >> S >> N;
vector<Item> items(N);
for (int i = 0; i < N; i++) {
cin >> items[i].value >> items[i].weight >> items[i].quantity;
}
long long result = solve_knapsack(S, items);
cout << result << endl;
return 0;
}
