#include<bits/stdc++.h>
using namespace std;
const int maks=2000;
const int maxitem=20000;
const int inf=2e9;
int s,n;
vector<pair<int,int> > weight[maks+5];
vector<pair<int,int> > item;
int dp[maxitem+5][maks+5];
int cek(int idx,int brt){
if(brt<0)return -inf;
if(idx==(long long)item.size())return 0;
int &res=dp[idx][brt];
if(res!=-1)return res;
auto[w,v]=item[idx];
return res=max(cek(idx+1,brt),cek(idx+1,brt-w)+v);
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>s>>n;
for(int r=0;r<n;r++){
int v,w,k;
cin>>v>>w>>k;
weight[w].push_back({v,k});
}
for(int d=1;d<=maks;d++){
sort(weight[d].begin(),weight[d].end());
int ambil= maks/d +1;
while(ambil!=0 && !weight[d].empty()){
auto &[v, k] = weight[d].back();
item.push_back({d, v});
k--;
ambil--;
if (k == 0) weight[d].pop_back();
}
}
memset(dp,-1,sizeof dp);
cout<<cek(0,s);
}
