#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
typedef long long llo;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int s,n;
cin >> s >> n;
map<int,vector<pair<int,int>>> w;
for (int i=0;i<n;i++){
int v,ww;
llo k;
cin >> v >> ww >> k;
k=min(k,(llo)s/ww);
w[ww].pb({v,k});
}
vector<pair<int,pair<int,int>>> v;
for (auto it:w){
sort(it.second.rbegin(),it.second.rend());
int y=0;
for (int i=0;i<it.second.size();i++){
if (y+it.second[i].second<=s){
v.pb({it.first,{it.second[i].first,it.second[i].second}});
y+=it.second[i].second;
}
else{
v.pb({it.first,{it.second[i].first,s-y}});
break;
}
}
}
vector<pair<int,int>> l;
for (int i=0;i<v.size();i++){
for (int j=0;j<v[i].second.second;j++){
l.pb({v[i].second.first,v[i].first});
}
}
vector<llo> dp(s+1,0);
for (int i=0;i<l.size();i++){
for (int j=s;j>=l[i].second;j--){
dp[j]=max(dp[j],dp[j-l[i].second]+l[i].first);
}
}
cout<<dp[s]<<endl;
}
