#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int f[10005],v[110],w[110],num[110]; int n,m; void OneZeroPack(int m,int v,int w) { for(int i=m;i>=v;i--)f[i]=max(f[i],f[i-v]+w); } void CompletePack(int m,int v,int w) { for(int i=v;i<=m;i++)f[i]=max(f[i],f[i-v]+w); } void MultiplePack(int m,int v,int w,int num){ if(vnum>=m){CompletePack(m,v,w);return ;} int k=1; for(k=1;k<=num;k<<=1){OneZeroPack(m,kv,kw);num=num-k;} if(num)OneZeroPack(m,numv,num*w); } int main(){ while(cin>>m>>n){ for(int i=0;i<n;i++)cin>>v[i]>>w[i]>>num[i]; memset(f,0,sizeof(f)); for(int i=0;i<n;i++)MultiplePack(m,v[i],w[i],num[i]); cout<<f[m]<<endl; } return 0; }