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