// https://oj.uz/problem/view/NOI18_knapsack
#include<bits/stdc++.h>
using namespace std;
#define ite(i,n) for(int i=0;i<n;i++)
#define itel(i,n) for(ll i=0;i<n;i++)
#define fora(i,a,b) for(int i=a;i<b;i++)
#define fors(i,a,b) for(int i=a;i>=b;i--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef std::set<ll>::iterator set_p ;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define reached cout<<"reached"<<endl
ll MOD=1e9+7;
/*--------------------------------------Printing functions start----------------------------------------------*/
template<typename T>
void print_vec(vector<T>&vec){
for(auto i=vec.begin();i!=vec.end();i++){
cout<<*i<<" ";
}
cout<<"\n";
}
template<typename T>
void print_2Dvec(vector<vector<T>>&vec){
for(int i=0;i<vec.size();i++){
for(int j=0;j<vec[i].size()>0;j++){
cout<<vec[i][j]<<"\t";
}
if(vec[i].size()>0)
cout<<"\n";
}
}
template<typename T, typename S>
void print_pair(pair<T,S> a){
cout<<a.first<<" "<<a.second<<"\n";
}
/*---------------------------------------Printing functions end-----------------------------------------------*/
/*---------------------------------------Graph functions------------------------------------------------------*/
// vector<int>dist(1e5+1,INT_MAX);
// vector<int>par(1e5+1, INT_MAX);
// vector<bool>visited(100001,0);
// vector<vector<int>>graph(2*(1e5)+1);
// template<typename T>
// void g_input(T n,T m){
// for(T i=0;i<m;i++){
// int a,b;
// cin>>a>>b;
// graph[a].push_back(b);
// graph[b].push_back(a);
// }
// }
// void bfs(int s){
// dist[s]=1;
// queue<int>q;
// q.push(s);
// while(!q.empty()){
// int t=q.front();
// q.pop();
// for(int i=0;i<graph[t].size();i++){
// if(dist[graph[t][i]]==INT_MAX){
// dist[graph[t][i]]=dist[t]+1;
// par[graph[t][i]]=t;
// q.push(graph[t][i]);
// }
// }
// }
// }
// void dfs(int n){
// visited[n]=1;
// // cout<<n<<"\n";
// for(int i=0;i<graph[n].size();i++){
// if(!visited[graph[n][i]]){
// dfs(graph[n][i]);
// }
// }
// }
/*---------------------------------------Graph functions------------------------------------------------------*/
// int main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// int s,n;
// cin>>s>>n;
// if(n==1){
// int v,w,k;
// cin>>v>>w>>k;
// int ans= min((s/w),k)*v;
// cout<<ans<<endl;
// return 0;
// }
// int v,w,k;
// vector<pii>list;
// list.push_back({0,0});
// ite(i,n){
// cin>>v>>w>>k;
// for(;k>0;k--){
// list.push_back({w,v});
// }
// }
// sort(list.begin(), list.end());
// n=list.size()-1;
// vector<vi>dp(2,vi(s+1,0));
// for(int i=1;i<n+1;i++){
// int x=i%2;
// for(int j=1;j<s+1;j++){
// if(j>=list[i].first) dp[x][j]=max(dp[x^1][j-list[i].first]+list[i].second, dp[x^1][j]);
// }
// }
// // print_2Dvec(dp);
// cout<<dp[n%2][s]<<endl;
// return 0;
// }
int main(){
fast;
map<ll,vector<pll>>m;
ll n,s;
cin>>s>>n;
itel(i,n){
int v,w,k;
cin>>v>>w>>k;
m[w].push_back({v,k});
}
vector<vll>dp(m.size()+1, vll (s+1,INT32_MIN)); //int32_min chosen to show the not possible case
dp[0][0]=0; // attaining 0 with a 0 weighted item is possible with maximum achieveble value to be 0
ll a=1;
for(auto& p : m){
ll w=p.first;
sort(p.second.begin(), p.second.end(), greater<pll>());
vector<pll> items = p.second;
for(int j=0;j<s+1;j++){
dp[a][j]=dp[a-1][j]; //considers the possibility of not choosing any items of the weight category w
// #important analyse it definitely
ll copies=0; // copies keeps track of many values of weight w have i used until now. It will not be updated to 0 after k_count reaches items[type].second
ll type=0; // basically keeps track of the type i am currentyl at in the items list. Type will be incremented when k_count reaches items[type].second
ll k_count=0; // keeps track if i reached k after eaach iteration. REset to 0 when it reaches items[type].second. Has to be incremented b4 the check
ll profit=0; //counts the total value being added at each weight type whilecomparing for the max imum value of dp[a][j]
/* what to do now: I need to maximise the value of each dp[a][j]. I can either choose some of the first category of items or the second as the items
are arranged in reverse order of value i can simply choose all of the first category of items before moving on to the second one. */
while((copies+1)*w<=j && type<items.size()){
copies++;
profit+=items[type].first;
if(dp[a-1][j-copies*w]!=INT32_MIN){
// dp[a][j]=max(dp[a-1][j-copies*w]+items[type].first,dp[a][j]); // Why will this line code not give the correct answer: Because while we are checking the addition of items[type].first we are not actually checking when the this particular value is being repeated again and again
dp[a][j]=max(dp[a-1][j-copies*w]+profit,dp[a][j]);
}
k_count++;
if(k_count == items[type].second){
k_count=0;
type++;
}
}
}
a++;
}
// print_2Dvec(dp);
cout<<dp[m.size()][s]<<endl;
}
