#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int MOD = 1e9+7;
const int INF = 1e9;
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;
for (auto [w, v] : mp) {
sort(v.rbegin(), v.rend());
// 0-1 knapsack
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';
}
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;
}
