#include <bits/stdc++.h>
using namespace std;
int s,n;
inline int iinput(){
int a=0;
int c=getchar_unlocked();
while (c<'0' || c>'9') c=getchar_unlocked();
while (c>='0' && c<='9'){
a=a*10 + c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//cin>>s>>n;
s=iinput(),n=iinput();
vector<pair<long long,long long>> l;
for (int i=0;i<n;i++){
long long v,w,k;
//cin>>v>>w>>k;
v=iinput(),w=iinput(),k=iinput();
long long j=1;
while (j<=k){
l.push_back({j*v,j*w});
k-=j;
j<<=1;
}
if (k>0) l.push_back({k*v,k*w});
}
vector<long long> dp(s+7,-1); //max value with weight
dp[0]=0;
for (auto [v,w]:l){
for (int i=s;i>=w;i--){
if (dp[i-w]==-1) continue;
dp[i]=max(dp[i],dp[i-w]+v);
}
}
long long ans=0;
for (int i=0;i<=s;i++) ans=max(ans,dp[i]);
cout<<ans<<"\n";
return 0;
}
