#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
const lld MOD=1e9+7;
const int MAX=3'000'000;
lld fact[MAX];
lld inv[MAX];
lld ModPow(lld base, lld exp){
if(exp==0)return 1;
if(exp%2==1)return (base*ModPow(base,exp-1))%MOD;
lld a=ModPow(base,exp/2);
return (a*a)%MOD;
}
lld comb(int a, int b){
if(b<0 || b>a)return 0;
lld ans=fact[a];
ans*=inv[b];
ans%=MOD;
ans*=inv[a-b];
ans%=MOD;
return ans;
}
void solve(){
int s,n;
cin>>s>>n;
vector<pair<lld,lld> >V;
vector<vector<lld> >best(s+1);
rep(i,0,n){
lld v,w,k;
cin>>v>>w>>k;
while(k>0){
int res=k%2;
if(res==0)res=2;
rep(j,0,res){
V.push_back({v,w});
}
k-=res;
k/=2;
v*=2;
w*=2;
}
}
trav(a,V){
if(a.second<=s){
best[a.second].push_back(a.first);
}
}
rep(i,0,s+1){
sort(best[i].begin(),best[i].end());
reverse(best[i].begin(),best[i].end());
while((lld)(best[i].size())*(lld)i>s){
best[i].pop_back();
}
}
vector<lld> DP(s+1,0);
rep(w,0,s+1){
trav(v,best[w]){
if(w<=s){
for(lld i=s;i-w>=0;i--){
DP[i]=max(DP[i],DP[i-w]+v);
}
}
}
}
cout<<DP[s]<<"\n";
}
int main(){
fact[0]=1;
rep(i,1,MAX)fact[i]=(i*fact[i-1])%MOD;
inv[MAX-1]=ModPow(fact[MAX-1],MOD-2);
for(int i=MAX-2;i>-1;i--)inv[i]=((i+1)*inv[i+1])%MOD;
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;
while(tt--){
solve();
}
}
