/*
ID: NAMIN
TASK:
LANG: C++
*/
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <numeric>
#include <math.h>
#include <set>
#include <unordered_set>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>
#include <fstream>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <assert.h>
#define gcd __gcd
#define endl "\n"
#define ll long long
#define ld long double
#define f first
#define s second
using namespace std;
const int MOD = 1e9+7;
void solve(){
//ifstream cin("snakes.in");
//ofstream cout("snakes.out");
int S,N;
cin >> S >> N;
ll dp[3][S+1];
memset(dp,-1e9,sizeof(dp));
int mod = 3;
for(int i=0;i<mod;i++)
dp[i][0] = 0;
for(int i=1;i<=N;i++){
ll v,x,k;
cin >> v >> x >> k;
for(int w=S;w>=0;w--){
dp[i%mod][w] = max(dp[i%mod][w],dp[(i-1)%mod][w]);
if(w-x >= 0 && dp[(i-1)%mod][w-x] != -1e9){
dp[i%mod][w] = max(dp[i%mod][w],dp[(i-1)%mod][w-x]+v);
}
}
k--;
bool ismore = true;
while(ismore && k--){
ismore = false;
for(int w=S;w>=0;w--){
//dp[i][w] = max(dp[i][w],dp[i-1][w]);
if(w-x >= 0 && dp[i%mod][w-x] != -1e9){
if(dp[i%mod][w] < dp[i%mod][w-x]+v){
ismore = true;
dp[i%mod][w] = max(dp[i%mod][w],dp[i%mod][w-x]+v);
}
}
}
}
}
ll ans = 0;
for(int i=0;i<=S;i++){
ans = max(ans,dp[N%mod][i]);
}
cout << ans << endl;
}
int main(){
// CHILL & \/\/\/\/\/\/\/
//[======================]
//|FOLLOW THE **METHODE**|
//[======================]
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
