#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int MOD = 1e9+7;
const int INF = 1e9;
/**
* https://oj.uz/problem/view/NOI18_knapsack
* Classical Multiple Knapsack Problem
* https://cp-algorithms.com/dynamic_programming/knapsack.html#multiple-knapsack
* Idea:
* Group items by weight, then sort by value descending since we want to take the most valuable items first.
* Use 0-1 knapsack to decide how many items to take from each group.
* dp[i][j] = max value using first i groups (weight type) with capacity j
* time complexity: (S^2log(S))
*/
// void solve() {
// int s, n;
// cin >> s >> n;
// map<int, vector<array<int, 2>>> mp;
// for (int i = 0; i < n; i++) {
// int v, w, k;
// cin >> v >> w >> k;
// if (w <= s) {
// mp[w].push_back({v, k});
// }
// }
// vector<vector<ll>> dp(mp.size() + 1, vector<ll>(s + 1, -1));
// dp[0][0] = 0;
// int idx = 1;
// // 0-1 knapsack
// for (auto [w, v] : mp) {
// sort(v.rbegin(), v.rend());
// for (int i = 0; i <= s; i++) {
// dp[idx][i] = dp[idx - 1][i];
// int j = 0;
// ll sumV = 0;
// int cnt = 0;
// int used = 0;
// while (j < v.size() && (cnt + 1) * w <= i) {
// cnt++;
// sumV += v[j][0];
// if (dp[idx - 1][i - cnt * w] != -1) {
// dp[idx][i] = max(dp[idx][i], dp[idx - 1][i - cnt * w] + sumV);
// }
// used++;
// if (used == v[j][1]) {
// used = 0;
// j++;
// }
// }
// }
// idx++;
// }
// ll ans = 0;
// for (int i = 1; i <= s; i++) {
// ans = max(ans, dp[mp.size()][i]);
// }
// cout << ans << '\n';
// }
void solve() {
int s, n;
cin >> s >> n;
map<int, vector<array<int, 2>>> mp;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
if (w <= s) {
mp[w].push_back({v, k});
}
}
vector<ll> dp(s + 1);
for (auto [w, ar]: mp) {
sort(ar.rbegin(), ar.rend());
for (auto [v, k] : ar) {
for (int c = 1; k > 0; c <<= 1) {
int take = min(k, c);
ll weight = 1ll * w * take;
ll value = 1ll * v * take;
if (weight > s) break;
for (int j = s; j >= weight; j--) {
dp[j] = max(dp[j], dp[j - weight] + value);
}
k-= take;
}
}
}
ll ans = *max_element(dp.begin(), dp.end());
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
// int T = 1;
// cin >> T;
// while (T--) {
solve();
// }
return 0;
}
