#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> W >> n;
vector<tuple<int, int, int>> arr(n + 5);
for (int i = 1; i <= n; i++) {
int v, w, k;
cin >> v >> w >> k;
k = min(k, W/w);
arr[i] = {v, w, k};
}
sort(arr.begin() + 1, arr.begin() + n + 1, greater<tuple<int, int, int>>());
vector<pair<int, int>> item;
vector<int> cnt(W + 5);
for (int i = 1; i <= n; i++) {
int v = get<0>(arr[i]), w = get<1>(arr[i]), k = get<2>(arr[i]), lim = min(k, W/w - cnt[w]);
for(int j = 1; j <= lim; j++) item.push_back({v, w}), cnt[w]++;
}
vector<int> dp(W + 5);
for (int i = 0; i < (int)item.size(); i++) {
vector<int> dq(dp);
int v = item[i].first, w = item[i].second;
for (int j = w; j <= W; j++) dq[j] = max(dq[j], dp[j - w] + v);
swap(dp, dq);
}
cout << dp[W] << '\n';
return 0;
}
