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