#include<bits/stdc++.h>
// #define int long long
#define ms(v) memset(v, -1, sizeof v)
#define pb push_back
#define mp make_pair
#define sz size
#define ll long long int
#define pi pair <int,int>
#define itn int
#define fr first
#define sc second
#define srt(v) sort(v.begin(), v.end())
#define rvs(v) reverse(v.begin(), v.end())
#define mod 1000000007
#define INF 1e6
#define N 100010
using namespace std;
itn n, s;
int v[N], ps[N], qtd[N];
map <pair <int, pi>, int> dp;
int solve(int pos, int peso, int quant){
if(peso < 0 or quant < 0) return -INF;
if(pos == 0) return 0;
// if(quant == 0) return solve(pos-1, peso, qtd[pos-1]);
if(dp.find({pos, {peso, quant}}) != dp.end()) return dp[{pos, {peso, quant}}];
// cout << pos << " " << peso << " " << quant << "\n";
dp[{pos, {peso, quant}}] = max(solve(pos-1, peso, qtd[pos-1]), solve(pos, peso - ps[pos], quant - 1) + v[pos]);
return dp[{pos, {peso, quant}}];
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> s >> n;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> ps[i] >> qtd[i];
if(qtd[i] > s/ps[i]){
qtd[i] = n/ps[i];
}
}
solve(n, s, qtd[n]);
// for(int i = 1;i <= n;i++){
// for(int j = 0;j <= s;j++){
// cout << dp[{i, {j, qtd[i]}}] << " ";
// }
// cout << "\n";
// }
cout << dp[{n, {s, qtd[n]}}] << "\n";
return 0;
}
