#include <bits/stdc++.h>
#include <climits>
using namespace std;
#define f first
#define s second
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define int long long
struct info{
int v,w,k;
};
const int N=1e5+5;
info M[N];
int s,n;
int dp[2000+5];
void solve(){
cin>>s>>n;
int ans=0;
for(int i=1;i<=n;++i) cin>>M[i].v>>M[i].w>>M[i].k;
for(int i=1;i<=n;++i){
int remain=M[i].k;
for(int k=1;remain>0;k<<=1){
int take=min(k,remain);
int wei=M[i].w*take,val=M[i].v*take;
remain-=take;
if(wei>s) continue;
for(int j=s;j>=wei;--j){
dp[j]=max(dp[j],dp[j-wei]+val);
ans=max(ans,dp[j]);
}
}
}
cout<<ans;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int T=1;
while(T--) solve();
}
