#include

#include

#include

#include

#include<string.h>

#include

#include

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;

}