#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int mxN = 2e5 + 5;
ll n,s,v1,w1,k1,dp[mxN];
multiset<pair<ll,ll>> st[2005];
vector<ll> v,w,k;
pair<ll,ll> x;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s >> n;
for(int i = 0; i < n; i++){
cin >> v1 >> w1 >> k1;
st[w1].insert({v1, k1});
}
ll curr;
for(int i = 1; i <= s; i++){
curr = 0;
auto it = st[i].end();
while(it != st[i].begin() and curr < s / i){
--it;
x = *it;
v.pb(x.first);
w.pb(i);
if(curr + x.second <= s / i){
k.pb(x.second);
curr += x.second;
}
else{
k.pb(s / i - curr);
curr = s / i;
}
}
}
n = v.size();
for(int i = 0; i < n; i++){
for(int j = s; j > 0; j--){
for(int l = 1; l <= k[i]; l++){
if(l * w[i] > j) break;
dp[j] = max(dp[j], dp[j - l * w[i]] + v[i] * l);
}
}
}
cout << dp[s];
}
