#include <bits/stdc++.h>
#define MiyaSoCute cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define int long long
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
using namespace std;
void solve(){
int s, n;
cin >> s >> n;
vector<int> V(n), W(n), K(n);
for(int i = 0; i < n; i++){
cin >> V[i] >> W[i] >> K[i];
}
vector<int> dp(s+1, 0);
for(int i = 0; i < n; i++){
int most = 0;
vector<pii> A;
for(int r = 1; r * 2 <= K[i]; r *= 2){
most += r;
A.pb({r*W[i], r*V[i]});
}
A.pb({(K[i]-most)*W[i], (K[i]-most)*V[i]});
for(int l = 0; l < A.size(); l++){
int curw = A[l].ff;
int curv = A[l].ss;
for(int w = s; w >= 0; w--){
if(w-curw >= 0){
dp[w] = max(dp[w-curw]+curv, dp[w]);
}
}
}
}
cout << dp[s] << '\n';
}
signed main(){
MiyaSoCute
int t = 1;
// freopen("stdin","r",stdin);
// freopen("stdout","w",stdout);
// cin >> t;
while(t--){
solve();
}
return 0;
}
/*
/\_/\
(= ._.)
/ > \>
*/
