#include <bits/stdc++.h>
using namespace std;
#define int long long
bool cmp(pair<int,pair<int,int>> &a, pair<int,pair<int,int>> &b) {
if (a.first == b.first) return a.second.first >= b.second.first;
return a.first < b.first;
}
const int S = 2005;
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int W, n;
cin>>W>> n;
vector<pair<int,pair<int,int>>> a;
for (int i=0; i<n; i++) {
int v,w,k;
cin>> v>> w>> k;
a.push_back({w, {v,k}});
}
sort(a.begin(), a.end(), cmp);
vector<pair<int,int>> e;
int prv=a[0].first;
int cnt=0;
for (auto &x : a) {
int w=x.first, v=x.second.first, k=x.second.second;
if (prv != w) {
cnt=0;
prv = w;
}
for (int i=0; i<k && cnt <= S/w; i++) {
cnt++;
e.push_back({v, w});
}
}
vector<int> dp(W+1, 0);
for (auto &x : e) {
for (int i=W; i>=x.second; i--) {
dp[i] = max(dp[i],dp[i-x.second]+x.first);
}
}
cout<< dp[W];
}
