#include <bits/stdc++.h>
using namespace std;
#define int long long
bool cmp(pair <int,int> a, pair <int, int > b){
return a.first > b.first;
}
vector< pair< int , int>> g[100005];
int dp[100005];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int s,n;cin>>s>>n;
for(int i=0;i<n;i++){
int v,k,w;
cin >> v >> w >> k;
if(w<=s)g[w].push_back({v,k});
}
vector<pair<int,int>> a;
for(int w=1;w<=s;w++){
auto& dsach = g[w]; if(dsach.empty()) continue;
sort(dsach.begin(), dsach.end(), cmp);
int sech = s/w, lay = 0;
for(auto p : dsach){
int v = p.first, k = p.second;
int c = min(k, sech - lay);
for(int i = 0; i < c; i++) a.push_back({w, v});
lay += c;
if(lay >= sech) break;
}
}
for(auto i:a){
int w = i.first; int v = i.second;
for(int j = s; j >= w; j--) dp[j] = max(dp[j], dp[j-w] + v);
}
cout<<dp[s];
}
