#include <iostream>
#include <vector>
#include <algorithm>
#define LL long long
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n,s;
std::cin>>s>>n;
int v,w,k;
std::vector<LL> dp(2001);
std::vector<std::pair<int,int>> group[2001];
for(int i=0;i<n;i++)
{
std::cin>>v>>w>>k;
group[w].emplace_back(v,k);
}
LL answer=0;
for(int i=0;i<=s;i++)
{ if(!group[i].empty()){
std::sort(group[i].begin(),group[i].end(),std::greater<std::pair<int,int>>());
int index=0;
for(int j=0;j<s/i;j++)
{
if(index>=group[i].size())break;
for(int k=s;k>=i;k--)
{
dp[k]=std::max(dp[k],dp[k-i] + group[i][index].first);
answer=std::max(answer,dp[k]);
}
group[i][index].second--;
if(group[i][index].second==0)index++;
}
}
}
std::cout<<answer<<'\n';
return 0;
}
