#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct Item {
int weight;
int value;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int S, N;
if (!(cin >> S >> N)) return 0;
vector<int> Weights(N);
vector<int> Values(N);
vector<int> Cnt(N);
for (int i = 0; i < N; ++i) {
cin >> Values[i] >> Weights[i] >> Cnt[i];
}
vector<Item> items;
for (int i = 0; i < N; ++i) {
int w = Weights[i];
int v = Values[i];
int c = Cnt[i];
int k = 1;
while (c > 0) {
int take = min(k, c);
items.push_back({w * take, v * take});
c -= take;
k *= 2;
}
}
vector<int> dp(S + 1, 0);
for (const auto& item : items) {
int w = item.weight;
int v = item.value;
for (int j = S; j >= w; --j) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[S] << "\n";
return 0;
}
