#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> matrix;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define down(i, b, a) for(ll i = b - 1; i >= a; i--)
struct info{
ll v, w, k;
info(){}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll s, n;
cin >> s >> n;
vector<info> a(n);
rep(i, 0, n){
cin >> a[i].v >> a[i].w >> a[i].k;
}
vi dp(s + 1, 0);
vi best(s + 1, 0);
rep(i, 0, n){
rep(mod, 0, a[i].w){
deque<ll> now;
rep(curr, 0, (s - mod) / a[i].w + 1){
while(!now.empty() && curr - now.front() > a[i].k){
now.pop_front();
}
while(!now.empty() && dp[now.back() * a[i].w + mod] + (curr - now.back()) * a[i].v <= dp[mod + curr * a[i].w]){
now.pop_back();
}
now.push_back(curr);
ll f = now.front();
best[mod + curr * a[i].w] = (curr - f) * a[i].v + dp[f * a[i].w + mod];
}
}
rep(j, 0, s + 1){
dp[j] = max(dp[j], best[j]);
}
}
cout << dp.back() << endl;
}
