#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int W,n,sum,i,j,msb;
cin>>W>>n;
vector<int> v(n),w(n),k(n),dp(W+1,0);
vector<vector<int>> a(W+1);
for(int i=0;i<n;i++) {
cin>>v[i]>>w[i]>>k[i];
msb=31;j=0;
sum=0;
while(!((k[i]>>msb)&1)) msb--;
while(j<msb) {
if(w[i]*(1LL<<j)<=W)
a[w[i]*(1LL<<j)].emplace_back(v[i]*(1LL<<j));
sum+=(1LL<<j);
j++;
}
if(k[i]-sum>0 && w[i]*(k[i]-sum)<=W)
a[w[i]*(k[i]-sum)].emplace_back(v[i]*(k[i]-sum));
}
for(int i=1;i<=W;i++) {
sort(a[i].begin(),a[i].end());
reverse(a[i].begin(),a[i].end());
for(int ww=W;ww>=1;ww--) {
sum = 0;
for(int j=0;j<a[i].size()&&i*(j+1)<=ww;j++) {
sum+=a[i][j];
dp[ww] = max(dp[ww],dp[ww-i*(j+1)]+sum);
}
}
}
int ans=0;
for(auto&x:dp)
ans = max(ans,x);
cout<<ans;
return 0;
}
