#include <bits/stdc++.h>
// solved by bekagg
#define int long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int N = 1e5+5;
const int MOD = 1e9+7;
int n , s , v[N] , w[N] , k[N];
int dp[N];
void arkanefury228(){
cin >> s >> n;
for (int i = 1; i <= n; i++){
cin >> v[i] >> w[i] >> k[i];
k[i] = min(k[i] , s);
}
for (int i = 1; i <= n; i++){
for (int cnt = 1; cnt <= k[i]; cnt++){
for (int j = s; j >= cnt * w[i]; j--){
dp[j] = max(dp[j] , dp[j - w[i]] + v[i]);
}
}
}
int ans = 0;
for (int i = 1; i <= s; i++) ans = max(ans , dp[i]);
cout << ans;
}
signed main(){
PRaim_bek_abi
int t=1;
//cin>>t;
for (int respagold = 1; respagold <= t; respagold++) arkanefury228();
}
