#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
//PBDS (Policy_Based_Data_Structure)
/*
Note - To use it as ordered multiset, change less<int> to less_equal<int>. Note that doing this swaps
the functions of lower_bound and upper_bound. So upper_bound now works as lower_bound and vice versa.
To erase an element, use oset.erase(oset.upper_bound(value));
*/
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// // find_by_order - oset.find_by_order(index) - returns element at that index
// order_of_key - oset.order_of_key(value) - return index of that element
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// // #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_set tree<string, null_type,less_equal<string>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define lld double
using ll = long long;
// using __int128=long long;
const int mod=998244353,MAXN=33,INF=1<<30,N=2e5+10;
#define F first
#define S second
#define pb push_back
#define mpp make_pair
#define all(v) v.begin(),v.end()
#define add(x,y) (x+y)%mod
#define mul(x,y) (((x%mod)*(y%mod))%mod)
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define nl "\n"
int MOD = 998244353;
const int TWO_MOD_INV = 500000004;
const ll maxn=5e3+10;
#define left(i) (2*i + 1)
#define right(i) (2*i + 2)
#define parent(i) ((i-1)/2)
#include <vector>
template<class T>
class SegmentTree
{
public:
//tree constructors.
SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
//query the range l to r, 0 based array indexing.
T query(int l, int r);
//update the element at index idx to val.
void update(int idx, T val);
///TODO lazy propagation
private:
//represents the segment tree.
T *tree;
//builds the segment tree.
void buildTree(std::vector<T> data);
//size of the segment tree array.
int segTreeSize;
//extra nodes must be added to array to make its size a power of 2
//this is the value to be filled for the those nodes.
T valueForExtraNodes;
//specifies how to combine child node results to form parent node result.
T (*combine)(T obj1, T obj2);
//used to calculate the size of array needed to store the tree.
int calculateSize(int n);
//helps to solve a range query.
T queryHelper(int l,int r, int st, int ed, int node);
};
template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
T value, T (*combine)(T obj1, T obj2))
{
this->combine = combine;
valueForExtraNodes = value;
segTreeSize = calculateSize(data.size());
buildTree(data);
}
template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
T value, T (*combine)(T obj1, T obj2))
{
this->combine = combine;
valueForExtraNodes = value;
segTreeSize = calculateSize(n);
std::vector<T> data;
for(int i = 0; i < n; i++)
data.push_back(ar[i]);
buildTree(data);
}
template<class T> int SegmentTree<T>::calculateSize(int n)
{
int pow2 = 1;
while( pow2 < n)
{
pow2 = pow2 << 1;
}
return 2*pow2 - 1;
}
template<class T> T SegmentTree<T>::query(int l, int r)
{
int st = 0, ed = segTreeSize/2;
return queryHelper(l, r, st, ed, 0);
}
template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
{
if( (r < st) || (l > ed) || (l > r) )
return valueForExtraNodes;
if(st >= l && ed <= r)
return tree[node];
T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
return combine(leftVal, rightVal);
}
template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
{
int n = data.size();
tree = new T[segTreeSize];
int extraNodes = (segTreeSize/2 + 1) - n;
for(int i = segTreeSize - 1; i >= 0; i--)
{
if(extraNodes>0)
{
tree[i] = valueForExtraNodes;
extraNodes--;
}
else if(n>0)
{
tree[i] = data[n-1];
n--;
}
else
tree[i] = combine(tree[left(i)], tree[right(i)]);
}
}
template<class T> void SegmentTree<T>::update(int idx, T val)
{
int segTreeIdx = (segTreeSize/2) + idx;
tree[segTreeIdx] = val;
while(parent(segTreeIdx) >= 0)
{
segTreeIdx = parent(segTreeIdx);
if(right(segTreeIdx) < segTreeSize)
tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
if(segTreeIdx == 0)
break;
}
}
//--------------------------------struct for overflow check-------------------------------------
// struct mi {
// int v;
// explicit operator int() const { return v; }
// mi() { v = 0; }
// mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
// };
// mi &operator+=(mi &a, mi b) {
// if ((a.v += b.v) >= MOD) a.v -= MOD;
// return a;
// }
// mi &operator-=(mi &a, mi b) {
// if ((a.v -= b.v) < 0) a.v += MOD;
// return a;
// }
// mi operator+(mi a, mi b) { return a += b; }
// mi operator-(mi a, mi b) { return a -= b; }
// mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); }
// mi &operator*=(mi &a, mi b) { return a = a * b; }
// mi pow(mi a, long long p) {
// assert(p >= 0);
// return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);
// }
// mi inv(mi a) {
// assert(a.v != 0);
// return pow(a, MOD - 2);
// }
// mi operator/(mi a, mi b) { return a * inv(b); }
//------------------------------------------------------
int inv(int i) {
return i <= 1 ? i : mod - (int)(mod/i) * inv(mod % i) % mod;
}
long long binpow(long long a, long long b, long long m=mod) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
void usaco(){
freopen("snakes.in", "r", stdin);
freopen("snakes.out", "w", stdout);
}
int minn(int a,int b){
return min(a,b);
}
void solve(){
int s,n;
cin>>s>>n;
int dp[s+1];
memset(dp,0,sizeof(dp));
vector<pair<int,int>> vc[s+1];
for(int i=0;i<n;i++){
int v,w,k;
cin>>v>>w>>k;
vc[w].pb({v,k});
}
for(int i=1;i<=s;i++){
// cout<<"YEH"<<nl;
sort(all(vc[i]));
reverse(all(vc[i]));
for(int j=1;j<vc[i].size();j++){
// cout<<"YEH"<<nl;
vc[i][j].S+=vc[i][j-1].S;
}
if(vc[i].size()==0){
continue;
}
int k=min(s/i,vc[i][vc[i].size()-1].S);
int val=0;
for(int j=1;j<=k;j++){
// cout<<k<<nl;
// cout<<"YEH"<<nl;
if(j>vc[i][val].S){
val++;
}
for(int l=s;l>=i;l--){
dp[l]=max(dp[l],vc[i][val].F+dp[l-i]);
}
}
}
int ans=0;
for(int i=0;i<=s;i++){
ans=max(ans,dp[i]);
}
cout<<ans<<nl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll t=1 ;
// usaco();
// cin>>t;
while(t--){
solve();
}
}
