#include<bits/stdc++.h>
using namespace std;
int n,m,v,w,c,dp[1005];
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&v,&w,&c);
if(c0){//完全背包
for(int j=v;j<=m;j++){
dp[j]=max(dp[j],dp[j-v]+w);
}
}
else if(c1){//01背包
for(int j=m;j>=v;j--){
dp[j]=max(dp[j],dp[j-v]+w);
}
}
else{//多重背包
for(int j=1;c;j<<=1){
int x=min(j,c);
for(int k=m;k>=vx;k--){
dp[k]=max(dp[k],dp[k-vx]+w*x);
}
c-=x;
}
}
}
printf("%d\n",dp[m]);
return 0;
}
