#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main(){
ll c,n;
cin>>c>>n;
vector<ll> dp(c+1, 0);
vector<vector<array<ll, 2>>> p(c+1);
for (int i=0; i<n; i++){
ll v,w,k;
cin>>v>>w>>k;
p[w].push_back({v, k});
}
//cout<<'a'<<endl;
for (int i=1; i<=c; i++) sort(p[i].rbegin(), p[i].rend());
//cout<<'b'<<endl;
for (int i=1; i<=c; i++){
//cout<<'c'<<endl;
if (p[i].empty()) continue;
ll s=c/i;
for (const auto [v, k]:p[i]){
//cout<<'d'<<endl;
auto r=min(k, s);
assert(r);
const auto lg=63-__builtin_clzll(r+1);
for (int j=0; j<lg; j++){
for (int m=c; m>=i<<j; --m){
dp[m]=max(dp[m], dp[m-(i<<j)]+(v<<j));
}
r-=1<<j;
}
//cout<<'e'<<endl;
//cout<<r<<' '<<i<<endl;
if (r) for (int j=c; j>=i*r; --j) dp[j]=max(dp[j], dp[j-i*r]+r*v);
s-=k;
if (s<=0) break;
//cout<<'f'<<endl;
}
}
cout<<dp.back()<<'\n';
}
