#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#define int long long
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define pqueue priority_queue
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,string> tp;
const int INF = 1e7 + 100;
const int MOD = 1e9 + 7;
const int maxN = 3100;
void _(){
int s,n;
cin >> s >> n;
vector<ii> a[s + 10];
for (int i = 0; i < n; i++){
int v,w,k; cin >> v >> w >> k;
a[w].eb(v,k);
}
vector<vector<int>> dp(s + 10,vector<int> (s+10,0));
// dp[i][j] = i ye kadar maks j weight alarak yapılabilecek best score;
int mx = 0;
for (int i = 1; i <= s; i++){
sort(all(a[i]),greater<ii>());
for (int j = 0; j <= s; j++){
dp[i][j] = max(dp[i][j],dp[i-1][j]);
if (a[i].empty()) continue;
int ptr = 0,add = 0,k = a[i][ptr].S,val = 0;
while (j + add + i <= s && ptr < a[i].size()){
val += a[i][ptr].F;
add += i;
k--;
dp[i][j + add] = max(dp[i][j + add],dp[i-1][j] + val);
mx = max(mx,dp[i][j + add]);
if (k == 0){
ptr++;
if (ptr == a[i].size()) break;
k = a[i][ptr].S;
}
}
}
}
cout << mx << endl;
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1; // cin >> t;
while (t--){
_();
}
return 0;
}
