#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define pb push_back
using vl=vector<ll>;
#define vvl vector<vl>
#define asort(v) sort(v.begin(),v.end())
#define dsort(v) sort(v.rbegin(),v.rend())
#define pll pair<ll,ll>
#define vpl vector<pll>
#define rev(v) reverse (v.begin(),v.end());
#define upb(vec, val) ((upper_bound((vec).begin(), (vec).end(), (val))) - (vec).begin())
#define lwb(vec, val) ((lower_bound((vec).begin(), (vec).end(), (val))) - (vec).begin())
#define sl set<ll>
#define spl set<pll>
#define in insert
#define c1 __builtin_popcountll
const ll mod = 1e9+7;
// const ll mx = 1e6;
int main() {
fast_io;
ll mx,n;
cin>>mx>>n;
vl v(n),w(n),c(n);
for(ll i=0;i<n;i++){
cin>>v[i]>>w[i]>>c[i];
}
vl dp(mx+1,0);
for(ll i=0;i<n;i++){
for(ll j=mx;j>=w[i];j--){
for(ll cp=1;cp<=c[i];cp++){
if( (cp*w[i]) > j )break;
dp[j]=max(dp[j],dp[j-cp*w[i]]+cp*v[i]);
}
}
}
cout<<dp[mx];
return 0;
}
