#include <bits/stdc++.h>
#define pb push_back
#define mod 1000000007
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
#define np next_permutation
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,j,n) for(int i=j;i<n;i++)
#define vii vector<vi>
#define vb vector<bool>
#define pr pair<int,int>
#define vl vector<ll>
#define vs vector<string>
#define us unordered_map<int,int>
#define Mpq priority_queue<int>
#define mpq priority_queue<int,vi,greater<int>>
#define eb emplace_back
#define pr pair<int,int>
#define prl pair<ll,ll>
#define vp vector<pr>
#define vpl vector<prl>
#define mkp make_pair
#define vi vector<int>
#define ld long double
#define vii vector<vi>
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
#define ull unsigned long long
#define prr pair<ll,int>
#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
typedef long long ll;
#define NUMERIC_LIMIT std::numeric_limits<std::streamsize>::max()
double epsilon=1e-8;
const int N=int(1e5)+1;
const ll INF=ll(1e18);
class Time{
private:
using clock_type = chrono::steady_clock;
using second_type = chrono::duration<double,ratio<1>>;
chrono::time_point<clock_type> m_init{clock_type::now()};
public:
void reset(){
m_init=clock_type::now();
}
double elapsed() const{
return
chrono::duration_cast<second_type>(clock_type::now()-m_init).count();
}
};
// int minp[N];
// void seive(){
// vb s(N,1);
// s[0]=s[1]=0;
// for(int i{};i<N;++i)
// minp[i]=i;
// for(int i=2;i*i<N;++i){
// if(!s[i]) continue;
// for(int j=i*i;j<N;j+=i){
// minp[j]=min(minp[j],i);
// s[j]=1;
// }
// }
// }
// vp divs(int x){
// vp d{};
// while(x>1){
// int p=minp[x];
// int cnt{};
// while(x>1 && x%p==0){
// x/=p;
// ++cnt;
// }
// d.eb(p,cnt);
// }
// return d;
// if(d.empty()) return vi{1};
// vi dv{};
// for(int c=0;c<=d[0].S;++c){
// dv.eb(pow(d[0].F,c));
// }
// for(int i=1;i<d.size();++i){
// vi tmp{};
// for(int c=0;c<=d[i].S;++c){
// int val=pow(d[i].F,c);
// for(int j=0;j<dv.size();++j)
// tmp.eb(dv[j]*val);
// }
// dv=tmp;
// }
// return dv;
// }
// ll add(ll x,ll y){
// x+=y;
// while(x>=mod) x-=mod;
// return x;
// }
ll s,n,v,w,c,ans;
ll dp[2001];
vector<prl> a[2001];
void solve(){
cin >> s >> n;
for(int i=0;i<n;++i){
cin >> v >> w >> c;
a[w].eb(v,c);
}
for(int i=1;i<=s;++i){
sort(all(a[i]),greater<prl>());
int cnt{};
for(int j=1;j<=(s/i);++j){
if(cnt>=a[i].size()) break;
for(int k=s;k>=i;--k){
dp[k]=max(dp[k],dp[k-i]+a[i][cnt].F);
ans=max(ans,dp[k]);
}
--a[i][cnt].S;
if(!a[i][cnt].S) ++cnt;
}
}
cout << ans << '\n';
}
int main(){
// #ifdef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int t{1};
// cin >> t;
for(int i=1;i<=t;i++){
// cout << "Case #" << i << ": ";
solve();
}
}
