#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define getbit(x,y) (((x)>>(y))&1)
#define turnon(x,y) ((x)|(1<<y))
#define turnof(x,y) ((x)^(1<<y))
#define oo 1000000000000000000
#define pb push_back
#define all(x) x.begin(),x.end()
#define con(mask) mask=(mask-1)&mask
#define Unique(val) val.erase(unique(val.begin(),val.end()),val.end())
int const N=1e5+10;
int f[N];
int w[N];
int v[N];
int a[N];
signed main()
{
cin.tie(0)->sync_with_stdio(false);
int s,n;
cin>>s>>n;
vector<pair<int,int>> oke;;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i]>>a[i];
int k=1;
while(a[i]>k){
oke.pb({v[i]*k,w[i]*k});
a[i]-=k;
k=k*2;
}
if(a[i]) oke.pb({v[i]*a[i],w[i]*a[i]});
}
for(auto x:oke){
for(int j=s;j>=x.second;j--){
f[j]=max(f[j],f[j-x.second]+x.first);
}
}
cout<<f[s]<<" ";
}
