#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
const int M = 1e5 + 5;
int S, N, V[M], W[M], K[M];
void solve1() {
vector<ll> dp(S+1, 0);
for (int i = 1; i <= N; i++) {
// consider ith item
for (int j = S; j >= W[i]; j--) {
// update weight sum j backward given Wi and Ki
for (int cnt = 1; cnt <= K[i]; cnt++) {
int wsum = cnt * W[i];
int vsum = cnt * V[i];
if (wsum <= j) dp[j] = max(dp[j], dp[j - wsum] + vsum);
}
}
}
cout << dp[S] << endl;
}
void solve2() {
vector<pair<int, int>> items_by[S+1];
for (int i = 1; i <= N; i++)
items_by[W[i]].push_back(make_pair(V[i], K[i]));
vector<ll> dp(S+1, 0);
for (int weight = 1; weight <= S; weight++) {
if (items_by[weight].empty()) continue;
sort(items_by[weight].rbegin(), items_by[weight].rend());
int idx = 0;
int cnt = 0;
while ((++cnt)*weight <= S && idx < items_by[weight].size()) {
int vi = items_by[weight][idx].first;
for (int j = S; j >= weight; j--)
dp[j] = max(dp[j], dp[j - weight] + vi);
if ((--items_by[weight][idx].second) == 0) idx++;
}
}
cout << dp[S] << endl;
}
int main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr);
cin >> S >> N;
int maxK = 0;
for (int i = 1; i <= N; i++) {
cin >> V[i] >> W[i] >> K[i];
maxK = max(maxK, K[i]);
}
if (N == 1) cout << V[1] * min(K[1], S/W[1]) << endl;
else if (N <= 100 && maxK <= 10) solve1();
else solve2();
return 0;
}
