#include<bits/stdc++.h>
#define ll long long
#define int ll
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define show cerr<<"*\n"
using namespace std;
void debug_out() {cout << '\n';}
template <typename Head, typename ...Tail>
void debug_out(Head H, Tail ...T){
cout << H << ' ';
debug_out(T...);
}
#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
void solve() {
int w, v, k, n, s; cin >> s >> n;
map<int, vector<pair<int,int>>> shop;
for(int i=0; i<n; i++) {
cin >> v >> w >>k;
if(w>s||k<=0) continue;
shop[w].push_back({v, k});
}
vector<vector<ll>> dp(s+5, vector<ll>(sz(shop)+1, INT64_MIN));
dp[0][0]=0;
int idx=1;
for(auto &[w, item]: shop) {
sort(all(item), greater<pair<int,int>>());
for(int i=1; i<=s; i++) {
dp[i][idx]=dp[i][idx-1];
int num =0, atp=0, ks=0;
ll gia=0;
while((num+1)*w<=i&&atp<sz(item)) {
num++;
ks++;
gia+=item[atp].first;
// debug(gia);
if(dp[i-num*w][idx-1]!=INT64_MIN) {
dp[i][idx]=max(dp[i][idx], dp[i-num*w][idx-1]+gia);
}
if(ks==item[atp].second) {
// debug(gia);
atp++;
ks=0;
}
}
}
idx++;
}
// debug(dp[1][1]);
ll ans =0;
for(int i=1; i<=s; i++) {
ans = max(ans, dp[i][idx-1]);
}
cout<< ans<<'\n';
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
// cin >> T;
while(T--)
solve();
}
