#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX_W = 2024;
vector<ll>dp(MAX_W, -1e18);
vector<pair<ll, ll>>vw[MAX_W];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int S, N; cin >> S >> N;
for(int i = 1; i <= N; i++){
ll v, w, k; cin >> v >> w >> k;
vw[w].emplace_back(v, k);
}
//each weight can only be taken S/w times
vector<pair<ll, ll>>v;
for(int i = 1; i <= S; i++){
if(vw[i].empty()) continue;
sort(vw[i].begin(), vw[i].end());
for(int j = 0; j < S/i; j++){
if(vw[i].empty()) break;
v.emplace_back(vw[i].back().first, i); //{val, weight}
vw[i].back().second--;
if(vw[i].back().second == 0) vw[i].pop_back();
}
}
dp[0] = 0;
for(auto &[val, wt]: v){
for(int i = S; i >= wt; i--) dp[i] = max(dp[i], dp[i - wt] + val);
}
ll ans = 0;
for(int i = 1; i <= S; i++) ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
