#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
struct MaxQueueTunada{ // Based on max-queue2.cpp taught in class
int ti, tf, delta;
deque< pair<int,int> > Q; // (val, time)
MaxQueueTunada(){
delta = ti = tf = 0;
Q.clear();
}
void push(int x){
x -= delta;
while(!Q.empty() && Q.back().first <= x)
Q.pop_back();
Q.push_back(pair<int,int>(x, tf++));
}
void pop(){
if(!Q.empty() && ti == Q.front().second)
Q.pop_front();
ti++;
}
int max(){ return (ti == tf ? 0ll : Q.front().first + delta); }
void addAll(int d){ delta += d; }
};
const int MAXN = 112345;
int C, N, V[MAXN], W[MAXN], K[MAXN];
void solve(){
cin >> C >> N;
for(int i = 1; i <= N; ++i)
cin >> V[i] >> W[i] >> K[i];
vector<int> dp_old(C + 1), dp_at = dp_old;
for(int i = 1; i <= N; ++i){
for(int rem = 0; rem <= min(C, W[i] - 1); ++rem){ // For each possible remainder value
MaxQueueTunada Q;
int ini = rem + ((C - rem) / W[i]) * W[i]; // place to start the window
int lo = ini; // leftmost index of the sliding window
for(int c = ini; c >= 0; c -= W[i]){ // Calculate dp_at[c] for each c in class 'rem'
if(c < ini){
Q.pop();
Q.addAll(-V[i]);
//cerr << "popei a queue e decrementei " << V[i] << " de todo mundo\n";
}
dp_at[c] = dp_old[c]; // dp[i][c] = dp[i-1][c]
while(lo >= 0 && (c - lo) / W[i] <= K[i]){ // Maintaining feasible sliding window
Q.push( V[i] * ((c - lo) / W[i]) + dp_old[lo]);
lo -= W[i];
}
//cerr << "sliding window esta em [" << lo + W[i] << ", " << c << "]\n";
dp_at[c] = Q.max();
//cerr << "O melhor foi " << dp_at[c] << "\n\n";
}
}
dp_old = dp_at;
}
cout << dp_at[C] << '\n';
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
//int t; cin>>t; while(t--)
solve();
return 0;
}
