#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define vt vector
#define pb push_back
#define F first
#define S second
void solve() {
int s,n; cin>>s>>n;
vt<vt<pair<int,int>>> item(s+1);
for (int i=0;i<n;i++){
int v,w,k; cin>>v>>w>>k;
k = min(k, (s+w-1)/w);
item[w].pb(make_pair(v, k));
}
vt<ll> dp(s+1, 0);
for (int w=1;w<=s;w++){
sort(all(item[w]), greater<>());
vt<int> values;
int cn = (s+w-1)/w;
for (auto [v,k]: item[w]){
if (cn-k<0) {
for (int i=0;i<cn;i++) values.pb(v);
break;
}
for (int i=0;i<k;i++) values.pb(v);
cn-=k;
}
for (int v: values){
for (int x=s;x>=w;x--){
dp[x] = max(dp[x], dp[x-w]+v);
}
}
}
cout << dp[s] << endl;
}
int main() {
int tt=1;
//cin>>tt;
while(tt--) solve();
return 0;
}
