#include<bits/stdc++.h>
#define ll long long
#define int ll
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define show cerr<<"*\n"
using namespace std;
void debug_out() {cout << '\n';}
template <typename Head, typename ...Tail>
void debug_out(Head H, Tail ...T){
cout << H << ' ';
debug_out(T...);
}
#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
void solve() {
int w, v, k, n, s; cin >> s >> n;
vector<vector<pair<int,int>>> shop(s+5);
vector<vector<ll>> dp(s+5, vector<ll>(s+5, -1));
for(int i=0; i<n; i++) {
cin >> v >> w >>k;
if(w>s) continue;
shop[w].push_back({v, k});
}
dp[0][0]=0;
for(int w=1; w<=s; w++) {
// if(!sz(shop[w])) continue;
sort(all(shop[w]), greater<pair<int,int>>());
for(int i=1; i<=s; i++) {
dp[i][w]=dp[i][w-1];
int num =0, atp=0, ks=0;
ll gia=0;
while((num+1)*w<=i&&atp!=sz(shop[w])) {
num++;
ks++;
gia+=shop[w][atp].first;
if(dp[i-num*w][w-1]!=-1) {
// debug(i, num , w);
dp[i][w]=max(dp[i][w], dp[i-num*w][w-1]+gia);
}
if(ks==shop[w][atp].second) {
// debug(gia);
atp++;
ks=0;
}
}
}
}
// debug(dp[1][1]);
ll ans=0;
for(int i=1; i<=s; i++) ans= max(ans, dp[i][s]);
cout<< ans<<'\n';
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
// cin >> T;
while(T--)
solve();
}
