#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int W, n;
cin >> W >> n;
vector<int> weight(n), value(n), cnt(n);
for(int i = 0; i < n; i++){
cin >> value[i] >> weight[i] >> cnt[i];
}
vector<int> dp(W + 1, 0);
// Process each item i
for(int i = 0; i < n; i++){
int w = weight[i];
int v = value[i];
int c = cnt[i];
// Binary-split the count c
for(int k = 1; c > 0; k <<= 1){
int take = min(k, c);
int ww = w * take;
int vv = v * take;
// 0/1 knapsack update for this pseudo-item
for(int cap = W; cap >= ww; cap--){
dp[cap] = max(dp[cap], dp[cap - ww] + vv);
}
c -= take;
}
}
cout << dp[W] << "\n";
return 0;
}
