#include <bits/stdc++.h>
using namespace std;
#define int long long // safety
int S, N;
vector<vector<int>> items;
vector<vector<int>> pref;
int dp[2005][2005];
int rec(int wt, int cap){
if(wt > S) return 0;
if(dp[wt][cap] != -1) return dp[wt][cap];
int ans = rec(wt + 1, cap); // take 0 items of this weight
int m = (int)pref[wt].size() - 1; // pref[wt][k] = sum of best k items
for(int take = 1; take <= m; take++){
if(take * wt <= cap){
ans = max(ans, pref[wt][take] + rec(wt + 1, cap - take * wt));
}else{
break;
}
}
return dp[wt][cap] = ans;
}
void solve(){
cin >> S >> N;
items.assign(S + 1, {});
pref.assign(S + 1, {});
for(int i = 0; i < N; i++){
int v, w, k;
cin >> v >> w >> k;
int use = min(k, S / w); // more than this can never fit
for(int j = 0; j < use; j++){
items[w].push_back(v);
}
}
for(int w = 1; w <= S; w++){
if(items[w].empty()) continue;
sort(items[w].rbegin(), items[w].rend());
int m = min((int)items[w].size(), S / w);
pref[w].assign(m + 1, 0);
for(int i = 1; i <= m; i++){
pref[w][i] = pref[w][i - 1] + items[w][i - 1];
}
}
memset(dp, -1, sizeof(dp));
cout << rec(1, S) << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
