#include<bits/stdc++.h>
#define int long long
#define ss second
#define ff first
#define pb push_back
const int mxn=1e6+5;
const int mod=998244353;
using namespace std;
int s,n,c;
int v[mxn+30],w[mxn+30];
int dp[2005];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>s>>n;
for(int i=1; i<=n; i++) {
int wi,vi,ki;
cin>>vi>>wi>>ki;
int t=1;
while(ki>=t) {
c++;
v[c]=vi*t;
w[c]=wi*t;
ki-=t;
t*=2;
}
if(ki>0) {
c++;
v[c]=vi*ki;
w[c]=wi*ki;
}
}
for(int i=1; i<=c; i++) {
for(int j=s; j>=w[i]; j--) {
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[s];
}
