#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[2005];
int32_t main() {
ios_base::sync_with_stdio(0),cin.tie(0);
int s,n;cin>>s>>n;
for(int i = 0 ; i<=s ; ++i) dp[i] = -1e18;
dp[0] = 0;
for(int i = 0 ; i<n ; ++i) {
int v,w,k;cin>>v>>w>>k;
for(int j = 0 ; j<=11 ; ++j) {
int num = min((1ll<<j),k);
k-=num;
for(int l = s ; l>=w*num; --l) {
if(dp[l-w*num] != -1e18) dp[l] = max(dp[l],dp[l-w*num]+v*num);
}
if(k == 0) break;
}
}
int ans = 0;
for(int i = 0 ; i<=s ; ++i) ans = max(ans,dp[i]);
cout << ans;
}
