#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int S, N;
if (!(cin >> S >> N)) return;
vector<int> Weights(N);
vector<int> Values(N);
vector<int> Cnt(N);
for (int i = 0; i < N; ++i) {
if (!(cin >> Values[i] >> Weights[i] >> Cnt[i])) return;
}
vector<pair<int, int>> 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<long long> dp(S + 1, 0);
for (const auto& item : items) {
int w = item.first;
int v = item.second;
for (int j = S; j >= w; --j) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[S] << endl;
}
int main() {
solve();
return 0;
}
