#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vint vector <int>
#define vll vector <ll>
#define vbool vector<bool>
#define pairint pair<int,int>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;
struct dta{
ll v, w, k;
};
void solve(ll tc){
ll s, n; cin >> s >> n;
vector<vector<pairll>> a(2001); ll v, w, k;
while(n--){
cin >> v >> w >> k;
if(k > 2000){
k = 2000;
}
a[w].pb({v, k});
}
for(int i = 1; i <= 2000; i++){
sort(a[i].begin(), a[i].end(), greater<pairll>());
}
vector<dta> c(1); ll tot;
for(ll i = 1; i <= 2000; i++){
tot = 0;
for(pairll x : a[i]){
if(tot >= s){
break;
}
c.pb({x.fi, i, x.sc});
tot += i*x.sc;
}
}
vector<vll> dp(c.size(), vll(s+1, 0));
for(ll i = 1; i < c.size(); i++){
for(ll j = 1; j <= s; j++){
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
for(ll k = 1; k <= c[i].k; k++){
if(j-c[i].w*k < 0){
break;
}
dp[i][j] = max(dp[i][j], dp[i-1][j-c[i].w*k] + c[i].v*k);
}
}
}cout << dp[c.size()-1][s] << endl;
}
int main(){
ll t; t = 1;
for(int i = 1; i <= t; i++){
solve(i);
}
}
