#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>b;i--)
#define repi(i,a,b) for(ll i=a;i<=b;i++)
#define rrepi(i,a,b) for(ll i=a;i>=b;i--)
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define ull unsigned ll
#define vvll vector<vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define endl '\n'
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define no cout << "NO" << endl;
#define yes cout << "YES" << endl;
using namespace std;
void solve(){
ll s,n;
cin >> s >> n;
vll dp(s + 1, 0 );
rep(i,0,n){
ll v,w,k;
cin >> v >> w >> k;
k = min(k ,s / w );
//cerr << k << endl;
for(ll z = 0; z < k ;z++){
for(ll j = s; j>=w;j--){
dp[j] = max(dp[j] , dp[j - w]+v);
}
}
}
cout << dp[s] << endl;
return;
}
int main() {
IO;
int t;
t = 1;
//cin >> t;
repi(i,1,t){
//cout<<"Case "<<i<<": ";
solve();
}
return 0;
}
