#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct item{
ll v, w, k;
};
bool cmpv(item a, item b){
return a.v > b.v;
}
void solve(){
ll S, n;
cin >> S >> n;
vector<item> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i].v >> a[i].w >> a[i].k;
}
vector<vector<item>> g(2001);
for(int i = 1; i <= n; i++){
g[a[i].w].push_back(a[i]);
}
vector<ll> dp(S+1, -INF);
dp[0] = 0;
auto add = [&](vector<ll> &f, item a) -> void{
for(int i = S; i >= 0; i--){
if(i-a.w >= 0) f[i] = max(f[i], f[i-a.w]+a.v);
}
};
for(int i = 1; i <= 2000; i++){
sort(g[i].begin(), g[i].end(), cmpv);
ll it = 0, cnt = 0;
if((int)g[i].size() == 0) continue;
for(int j = 1; j <= S/i; j++){
cnt++;
if(cnt > g[i][it].k){
cnt = 1;
it++;
}
if(it >= (int)g[i].size()) break;
add(dp, g[i][it]);
}
}
ll ans = -1;
for(int i = 0; i <= S; i++) ans = max(ans, dp[i]);
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
