#pragma GCC optimize("O5,unroll-loops,inline,omit-frame-pointer")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#include<bits/stdc++.h>
#define int long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
int n,m,dp[2005];
signed main(void){
exoworldgd;
cin>>n>>m;
for(int i=0,v,w,k;i<m;i++){
cin>>v>>w>>k;
for(int p=1;p<=k;p<<=1){
for(int j=n;j>=w*p;j--)dp[j]=max(dp[j],dp[j-w*p]+v*p);
k-=p;
}
if(k)for(int j=n;j>=w*k;j--)dp[j]=max(dp[j],dp[j-w*k]+v*k);
}
cout<<dp[n];
}
