#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;
}

#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; }

#include <iostream>
#include <cmath>
#include <cstring>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int w[N],v[N],dp[N],n,m,len ,ww,vv,num;
int main(){
	cin >> m >> n;
	for(int i=1; i<=n ;i++)
	{
		cin >> ww >> vv >> num;
		int cnt = 1;
		while(cnt <= num){
			w[++len]=cnt*ww;
			v[len]=cnt*vv;
			num -= cnt;
			cnt <<= 1;
		}
		if(num > 0){
			w[++len]=num*ww;
			v[len]=num*vv;
		}
		
	}
	n = len;
	for(int i=1; i<=n; i++)
	{
		for(int j=m; j>=w[i]; j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout << dp[m];
	return 0;
}//二进制解法

#include<iostream>

#include<queue>

#include<map>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<cstdio>

using namespace std;

const int N=6e3+10;

const int INF=0x3f3f3f3f;

int m,n,w[N],v[N],dp[N],i,j,ww,vv,len,num1,cnt=1;

int main(){

cin>>m>>n;

for(i=1;i<=n;i++){

	cin>>ww>>vv>>num1;

	cnt=1;

	while(cnt<=num1){

		w[++len]=cnt*ww;

		v[len]=cnt*vv;

		num1-=cnt;

		cnt<<=1;

	}

	if(num1>0){

		w[++len]=num1*ww;

		v[len]=num1*vv;

	}

}

n=len;

for(i=1;i<=n;i++){

	for(j=m;j>=w[i];j--){

		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

	}

}

cout<<dp[m]<<endl;

return 0;

}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int N,V,dp[210];
struct node
{
    int n;//空间
    int c;//价值
    int w;//数量
} p[210];
int main()
{
    scanf("%d%d",&V,&N);
    for(int i=1; i<=N; i++)
        scanf("%d%d%d",&p[i].n,&p[i].c,&p[i].w);
    for(int i=1; i<=N; i++)
    {
        if(p[i].w*p[i].n>=V)
        {
            for(int j=p[i].n; j<=V; j++)
                dp[j]=max(dp[j],dp[j-p[i].n]+p[i].c);
        }
            for(int k=1; k<p[i].w; p[i].w-=k,k=k*2)
                for(int j=V; j>=k*p[i].n; j--)
                    dp[j]=max(dp[j],dp[j-k*p[i].n]+p[i].c*k);
            for(int j=V; j>=p[i].n*p[i].w; j--)
                dp[j]=max(dp[j],dp[j-p[i].w*p[i].n]+p[i].c*p[i].w);
    }
    printf("%d\n",dp[V]);
    return 0;
}