#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(v*num>=m){CompletePack(m,v,w);return ;}
    int k=1;
    for(k=1;k<=num;k<<=1){OneZeroPack(m,k*v,k*w);num=num-k;}
    if(num)OneZeroPack(m,num*v,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;
}