#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, MAXS = 2005;
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int lim, numVal;
long long dp[MAXS];
struct Node{
int V, W, N;
Node(int _V = 0, int _W = 0, int _N = 0):
V(_V), W(_W), N(_N) {};
} val[MAXN];
void input(){
cin >> lim >> numVal;
for(int i = 1; i <= numVal; i++)
cin >> val[i].V >> val[i].W >> val[i].N;
}
bool cmp(const Node &a, const Node &b){
return (a.W < b.W || (a.W == b.W && a.V > b.V));
}
void solve(){
memset(dp, -0x3f, sizeof dp);
dp[0] = 0;
int rep = 0;
for(int i = 1; i <= numVal; i++){
if (val[i].W != val[i - 1].W) rep = lim / val[i].W;
for(int j = 0; j < min(rep, val[i].N); j++){
for(int k = lim - val[i].W; k >= 0; k--){
maximize(dp[k + val[i].W], dp[k] + val[i].V);
}
}
rep -= min(rep, val[i].N);
}
long long res = -1e18;
for(int i = 0; i <= lim; i++) maximize(res, dp[i]);
cout << res << '\n';
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
input();
solve();
}
