#include <bits/stdc++.h>
using namespace std;
#define N 300005
#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second
ll T, n, s, dp[N];
vector <pair<ll,ll>> v1, v2[N];
int main(){
cin >> s >> n;
for(int i = 1; i <= n; i++){
ll v, w, k;
cin >> v >> w >> k;
v2[w].push_back({-v,k});
}
for(int i = 1; i <= s; i++){
if(sz(v2[i]) > 0){
sort(v2[i].begin(), v2[i].end());
ll x = (s/i);
for(auto j : v2[i]){
for(int j1 = 1; j1 <= min(x,j.ss); j1++){
v1.push_back({-j.ff,i});
}
x -= min(x,j.ss);
}
}
}
for(auto i : v1){
int v = i.ff, w = i.ss;
for(int j = s; j >= 0; j--){
if(dp[j] != 0 or j == 0){
dp[j + w] = max(dp[j] + v, dp[j + w]);
}
}
}
ll mx = 0;
for(int i = 1; i <= s; i++){
mx = max(dp[i],mx);
}
cout << mx;
return 0;
}
