#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 7;
int dp[N];
vector<pii> item[N];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int s, n; cin >> s >> n;
for (int i = 1; i <= n; i++) {
int v, w, k; cin >> v >> w >> k;
item[w].push_back({v, k});
}
for (int w = 1; w <= s; w++) {
sort(item[w].begin(), item[w].end(), greater<pii>());
int sum = 0;
for (auto [v, k] : item[w]) {
while (sum + w <= s && k) {
k--;
sum += w;
for (int i = s; i >= w; i--) dp[i] = max(dp[i], dp[i - w] + v);
}
if (sum + w > s) break;
}
}
cout << dp[s] << '\n';
return 0;
}
