//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e15;
const ll MAXN=10000006,MAXS=2006;//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 1e7
ll n,ans,s,k,v,w,cnt,dp[MAXS];
struct node{
ll v,w;
}lst[MAXN];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>s>>n;
for(int i=1;i<=n;i++){
cin>>v>>w>>k;
ll now=1;
while(k>=now){
k-=now;
lst[++cnt].v=v*now;
lst[cnt].w=w*now;
now*=2;
}
if(k){
lst[++cnt].v=v*k;
lst[cnt].w=w*k;
}
}
for(int i=1;i<=cnt;i++){
for(int j=s;j>=lst[i].w;j--){
dp[j]=max(dp[j],dp[j-lst[i].w]+lst[i].v);
ans=max(ans,dp[j]);
}
}
cout<<ans<<'\n';
}
