#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int INF = (int)(1e9)+2;
const int mod1 = (int)(1e9)+7;
bool isprime(int n){
if(n==1)
return 0;
for(int i=2;i<=(int)(sqrt(n));i++){
if(n%i==0)
return 0;
}
return 1;
}
int moduloinverse(int a,int p){
int power=p-2;
int curr=a;
int ans=1;
while(power>0){
if(power & 1)
ans=((ans%p)*(curr%p))%p;
curr=((curr%p)*(curr%p))%p;
power/=2;
}
return ans%p;
}
int binexp(int a,int b,int m){
int ans=1;
int curr=a;
while(b>0){
if(b&1)
ans=((ans%m)*(curr%m))%m;
curr=((curr%m)*(curr%m))%m;
b/=2;
}
return ans%m;
}
int __lcm(int a,int b){
return (a*b)/__gcd(a,b);
}
/*****************************TOTIENT FUNCTION***********************************/
//totient function
//TC->O(sqrt(n))
int phi(int n){
//phi(n)=number of integers from 1 to n inclusive that are co prime to n
//phi(p)=p-1, p->prime
//phi(p^k)=p^k-p^(k-1), p->prime, k>=1
//phi(ab)=phi(a)*phi(b)*d/phi(d), d->gcd(a,b) //todo
//phi(n)=n(1-1/p1)(1-1/p2)....(1-1/pk)
int result = n;
for(int i=2;i*i<=n;i++){
if(n%i == 0){
while(n%i == 0){
n=n/i;
}
result-=result/i;
}
}
if(n>1){
result-=result/n;
}
return result;
}
//totient function sieve
//TC->O(nloglogn)
vector<int> phiv;
void phi1_n(int n){
phiv.resize(n+1);
for(int i=0;i<=n;i++){
phiv[i]=i;
}
for(int i=2;i<=n;i++){
if(phiv[i]==i){
for(int j=i;j<=n;j+=i){
phiv[j]-=phiv[j]/i;
}
}
}
}
//divisor sum property: summation phi(d)=n , d|n
//Euler theorem a^(phi(m)) = 1 (mod m)
/*******************************END**********************************/
/***************************SEGMENT TREE*****************************/
vector<ll> seg;
vector<ll> lazy;
void initseg(int n){
seg.assign(4*n+4,0);
lazy.assign(4*n+4,0);
}
void buildseg(vector<ll>& a,ll idx,ll l,ll r) {
if (l == r) seg[idx] = a[l];
else {
ll mid = (l + r) / 2;
buildseg(a, idx*2, l, mid);
buildseg(a, idx*2+1, mid+1, r);
seg[idx] = seg[idx*2] + seg[idx*2+1]; // change function here
}
}
void push(ll idx,ll l,ll r){
// Default : addition operation
ll mid = (l+r)/2;
seg[2*idx]+=(mid-l+1)*lazy[idx];
lazy[2*idx]+=lazy[idx];
seg[2*idx+1]+=(r-mid)*lazy[idx];
lazy[2*idx+1]+=lazy[idx];
lazy[idx]=0; // change identity here
}
ll queryseg(ll idx,ll l,ll r,ll lq,ll rq) {
if (l>rq || r<lq) return 0; //change identity here
if (l>=lq && r<=rq) return seg[idx];
push(idx,l,r);
ll mid = (l + r) / 2;
return queryseg(idx*2, l, mid, lq, rq) + queryseg(idx*2+1, mid+1, r, lq, rq); //change function here
}
void updateseg(ll idx,ll l,ll r,ll pos,ll new_val) {
if (l == r) seg[idx] = new_val; //change depending on type of update
else {
ll mid = (l + r) / 2;
if (pos <= mid) updateseg(idx*2, l, mid, pos, new_val);
else updateseg(idx*2+1, mid+1, r, pos, new_val);
seg[idx] = seg[idx*2] + seg[idx*2+1]; // change function here
}
}
void upranseg(ll idx,ll l,ll r,ll lu,ll ru,ll addend) {
// Default: addition update operation, sum query operation
if (l>ru || r<lu) return;
if (l>=lu && r<=ru) {
seg[idx] += (r-l+1)*addend; // change function here
lazy[idx] += addend; // change function here
}
else {
push(idx,l,r);
ll mid = (l + r) / 2;
upranseg(idx*2, l, mid, lu, ru, addend);
upranseg(idx*2+1, mid+1, r, lu, ru, addend);
seg[idx] = seg[idx*2] + seg[idx*2+1]; // change function here
}
}
/*********************************END****************************************/
/********************POLYNOMIAL ROLLING HASH FUNCTION************************/
int compute_hash(string &s){
int mod = (int)(1e9)+9;
int p = 31;
int hash_val = 0;
int p_pow=1;
for(auto ch : s){
hash_val=(hash_val+((ch-'a'+1)*p_pow)%mod)%mod;
p_pow=(p_pow*p)%mod;
}
return hash_val;
}
int count_unique_substrings(string &s){
//TC->O(n^2)
int n = s.size();
vector<int> p_pow(n);
p_pow[0]=1;
int p=31;
int m = (int)(1e9)+9;
for(int i=1;i<n;i++)
p_pow[i]=(p_pow[i-1]*p)%m;
vector<int> hashes(n+1,0); //hashes[i] stores the prefix hash of first i characters
hashes[0]=0;
for(int i=0;i<n;i++){
hashes[i+1]=(hashes[i]+((s[i]-'a'+1)*p_pow[i])%m)%m;
}
int cnt=0;
for(int l=1;l<=n;l++){
set<int> hs;
for(int i=0;i<=n-l;i++){
int curr_hash=(hashes[i+l]-hashes[i]+m)%m;
curr_hash=(curr_hash*p_pow[n-i-1])%m;
hs.insert(curr_hash);
}
cnt+=hs.size();
}
return cnt;
}
/************************************END*************************************/
/**************************************LIS**************************************/
// int lis(vector<int>&a){ //1-indexed size(a)=n+1
// int n = a.size()-1;
// vector<int> helper; //helper[i] gives minimum last value for an lis of length i
// for(int i=1;i<=n;i++){
// if(helper.empty() || helper.back()<a[i]){
// helper.push_back(a[i]);
// }
// else{
// auto it = lower_bound(helper.begin(),helper.end(),a[i]);
// *(it)=a[i];
// }
// }
// return helper.size();
// }
/***************************************END**************************************/
/***************************LCA-BINARY LIFTING**********************************/
//vector<vector<int>> up;
//vector<vector<int>> g;
//vector<pair<int,int>> tt;
//int l;
// void initlca(int n){
// tt.clear();
// up.clear();
// tt.resize(n+1);
// l = ceil(log2(n));
// up.resize(n+1,vector<int>(l+1,-1));
//}
// void dfslca(int node,int parent,int &ti){ //initially node=parent=1;ti=0;
// up[node][0]=parent;
// tt[node].first=ti;
// for(int i=1;i<=l;i++){
// up[node][i]=up[up[node][i-1]][i-1];
// }
// ti++;
// for(auto neigh : g[node]){
// if(neigh!= parent){
// dfslca(neigh,node,ti);
// }
// }
// tt[node].second=ti;
// ti++;
// }
// int check(int a,int b){
// if(tt[a].first<=tt[b].first && tt[a].second>=tt[b].second) return 1; return 0;
// }
// int lca(int a,int b){
// if(check(a,b)){
// return a;
// }
// if(check(b,a)){
// return b;
// }
// int st=l;
// int anc=a;
// while(st>-1 && (!(check(anc,b)==0 && check(up[anc][0],b)==1))){
// if(check(up[anc][st],b)){
// st--;
// }
// else{
// anc=up[anc][st];
// st--;
// }
// }
// return up[anc][0];
// }
/**********************************END*************************************/
// struct minstack{
// stack<pair<int,int>> st;
// int getmin() {return st.top().second;}
// bool empty() {return st.empty();}
// void push(int ele){
// int mini=ele;
// if(!empty()){
// mini=min(mini,st.top().second);
// st.push({ele,mini});
// }
// }
// void pop(){
// st.pop();
// }
// int top(){
// return st.top().first;
// }
// };
// struct minqueue{
// stack<pair<int,int>> s1,s2;
// int getmin(){
// int mini;
// if(s1.empty() || s2.empty()){
// mini = (s1.empty())?(s2.top().second):(s1.top().second);
// }
// else{
// mini=min(s1.top().second,s2.top().second);
// }
// return mini;
// }
// void push(int ele){
// int mini;
// mini = (s1.empty())?(ele):(min(ele,s1.top().second));
// s1.push({ele,mini});
// }
// void pop(){
// if(s2.empty()){
// while(!s1.empty()){
// int element = s1.top().first;
// s1.pop();
// int newmini;
// newmini = (s2.empty())?(element):(min(element,s2.top().second));
// s2.push({element,newmini});
// }
// }
// int remove_element=s2.top().first;
// s2.pop();
// }
// };
int dp[2001][2001];
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--){
int s,n;
cin>>s>>n;
vector<int> cnt;
vector<vector<int>> values;
vector<set<pair<int,int>,greater<pair<int,int>>>> v(s+1);
for(int i=1;i<=n;i++){
int vi,w,k;
cin>>vi>>w>>k;
cnt.push_back(w);
v[w].insert({vi,k});
}
cnt.push_back(-1);
// for(auto i : cnt){
// cout<<i<<endl;
// }
// cout<<"Hi"<<endl;
sort(cnt.begin(),cnt.end());
auto it = unique(cnt.begin(),cnt.end());
cnt.resize(distance(cnt.begin(),it));
int num=cnt.size()-1;
values.resize(num+1);
// cout<<num<<endl;
for(int i=1;i<=num;i++){
for(auto j : v[cnt[i]]){
int flag=0;
for(int k=0;k<j.second;k++){
values[i].push_back(j.first);
if(values[i].size()==2000){
flag=1;
break;
}
}
if(flag){
break;
}
}
}
// for(int i=1;i<=num;i++){
// cout<<i<<endl;
// for(auto j : values[i]){
// cout<<j<<" ";
// }
// cout<<endl;
// }
// cout<<"*****"<<endl;
for(int i=0;i<=num;i++){
for(int j=0;j<=s;j++){
if(i==0){
dp[i][j]=0;
continue;
}
if(j==0){
dp[i][j]=0;
continue;
}
else{
dp[i][j]=dp[i-1][j];
int temp=0;
if(j>=cnt[i]){
for(int l=0;l<(j/cnt[i]);l++){
if(l>=values[i].size()){
break;
}
temp+=values[i][l];
dp[i][j]=max(dp[i][j],dp[i-1][j-(l+1)*cnt[i]]+temp);
}
}
}
}
// for(int j=0;j<=s;j++){
// cout<<i<<" "<<j<<endl;
// cout<<dp[i][j]<<endl;
// }
}
cout<<dp[num][s]<<endl;
}
return 0;
}
