/////////////////////////////////////////////////////////////////
//////// Born_To_Laugh - Hughie Do ////////
/////////////////////////////////////////////////////////////////
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=3e5+5;
const int INF=1e9+7;
/*
Idea:
*/
void solve(){
map<int,vector<pair<int,int>>> wei;
int s, t;
cin >> s >> t;
while(t--){
int v, w, k;
cin >> v >> w >> k;
if(w <= s){
wei[w].push_back(make_pair(v,k));
}
}
vector<int> dp(s+1, 0);
for(int i=0; i<=s; ++i){
if(wei[i].size() == 0)continue;
sort(wei[i].begin(), wei[i].end(), greater<pair<int,int>>());
int index = 0;
//xet j so dau tien co can nang i
for(int j=0; j*i<=s; ++j){
if(index >= wei[i].size())break;
for(int k = s; k>=i; --k){
dp[k]=max(dp[k], dp[k-i]+wei[i][index].first);
}
wei[i][index].second--;
if(wei[i][index].second == 0)index++;
}
}
cout << dp[s];
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
return 0;
}
/*
Use for suggestion:
{
while
}
{
nullptr
sync_with_stdio
false
return
to_string
length
}
{
push_back
pop_back
sort
reverse
begin
end
distance
assign
}
{
insert
erase
lower_bound
upper_bound
binary_search
}
{
first
second
swap
}
{
double
float
unsigned
}
{
unordered_map
pair
vector
deque
string
auto
cout
}
*/
