#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e3 + 10;
int dp[MAXN];
vector<pair<int, int>> group[MAXN];
vector<int> weights[MAXN];
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
int s, n; cin >> s >> n;
int max_w = 0;
for(int i=1; i<=n; i++){
int v, w, k; cin >> v >> w >> k;
group[w].push_back({v, k});
max_w = max(max_w, w);
}
for(int i=1; i<=max_w; i++){
sort(group[i].begin(), group[i].end());
int sz = 0;
while(sz < (s / i) && !group[i].empty()){
if(group[i].back().second == 0){
group[i].pop_back();
continue;
}
weights[i].push_back(group[i].back().first);
group[i].back().second --;
sz ++;
}
}
for(int i=1; i<=max_w; i++){
for(auto v : weights[i]){
for(int j=s; j>=0; j--){
if(i <= j) dp[j] = max(dp[j], dp[j - i] + v);
}
}
}
cout << dp[s] << "\n";
return 0;
}
