#include <bits/stdc++.h>
using namespace std;
int S, N;
const int MS = 2001;
vector<pair<int,int>> items[MS]; //items[w] contains {-v,k}
vector<pair<int,int>> final_items; //contains {w, v}
int dp[MS] = {};
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> S >> N;
for(int i = 0; i < N; i++){
int v, w, k; cin >> v >> w >> k;
if(w <= S){
items[w].push_back({-v,k});
}
}
//we only need to consider the first floor(S/w) items of weight w
for(int w = 0; w <= S; w++){
sort(items[w].begin(), items[w].end());
int total = 0;
for(pair<int,int> p : items[w]){
int v = -p.first; int k = p.second;
if(total + k < S/w){
for(int i = 0; i < k; i++) final_items.push_back({w, v});
total += k;
} else if(total < S/w){
for(int i = 0; i < S/w-total; i++) final_items.push_back({w, v});
break;
}
}
}
//now, a classic knapsack dp:
for(pair<int,int> p : final_items){
int w = p.first; int v = p.second;
for(int i = S; i >= w; i--){
dp[i] = max(dp[i], dp[i-w] + v);
}
}
cout << dp[S];
return 0;
}
